我为什么一看见这题就想用树状数组，又好写，又实用，多好。。。 nlogn建树，单词查询logn，对于100000的数据绰绰有余。 不过这好像和一般的树状数组不一样，一般都是求和，这次是求最值，变一下查询函数query。
//a[i]代表第i个数字，t[i]就是树状数组 //函数过程：每次强制让r指针进入下一棵子树（r--），在防止r指针出查询界限的同时（r-l>=lowbit(r)）， //不断跳跃（r-=lowbit(r)），并用r指针更新答案，直到剩余查询区间长度为0时退出（l==r）。 int query(int l,int r){ int ans=a[r]; while(1){ ans=min(ans,a[r]); if(l==r)break; for(r--;r-l>=lowbit(r);r-=lowbit(r)){ ans=min(ans,t[r]); } } return ans; }除了这个，也没什么了。 我可能讲的不好，大家可以百度“树状数组求区间最值”，自己学。 下面是完整代码：
#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; int n,m; int a[1000001]; int t[1000001]; inline int lowbit(int x){ return x&-x; } void add(int i,int x){ while(i<=n){ t[i]=min(t[i],x); i+=lowbit(i); } } int query(int l,int r){ int ans=a[r]; while(1){ ans=min(ans,a[r]); if(l==r)break; for(r--;r-l>=lowbit(r);r-=lowbit(r)){ ans=min(ans,t[r]); } } return ans; } int main(){ memset(t,0x3f,sizeof(t)); scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); add(i,a[i]); } for(int i=1,j=m;j<=n;i++,j++){ printf("%d\n",query(i,j)); } return 0; }