期中考挂完又来划水啦…
然后在洛谷上随机抽了一题
然后发现好像以前在哪里见过这个（后来发现是rxz的blog）
一开始是想到写st表，然后蜜汁三个点爆了内存QAQ…
后来想起了这道题…就去翻了下那篇blog，学了下单调队列…
然后我的做法应该挺大众的
就以维护最小值为例，在队列里记录队列里每个元素进队的位置（时间）
每次直接把要弹出去的队首元素弹出去，然后对于要新加入的元素$a[i]$跟队尾元素比较，如果比他大就直接弹出去（因为我们要的是最小值所以比他大的话就没有用了）
一直弹到不能弹，然后在把$a[i]$加到队尾，最大值也同理
因为在每次维护最值的时候每个元素最多只会进出队列一次，所以复杂度就是$O(n)$了
我写的好像有点长…
OwO
#include<cstdio> #include<deque> #include<cstring> #include<algorithm> using namespace std; const int N=1000005; inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } int n,k; int a[N]; struct point { int tim,val; point(int t,int v):tim(t),val(v){} }; deque<point>q; inline void solve1() { for(register int i=1;i<=k;i++) { while(!q.empty()&&q.back().val>a[i])q.pop_back(); q.push_back(point(i,a[i])); } printf("%d ",q.front().val); for(register int i=k+1;i<=n;i++) { while(!q.empty()&&q.front().tim+k-1<i)q.pop_front(); while(!q.empty()&&q.back().val>a[i])q.pop_back(); q.push_back(point(i,a[i])); printf("%d ",q.front().val); } printf("\n"); } inline void solve2() { while(!q.empty())q.pop_back(); for(register int i=1;i<=k;i++) { while(!q.empty()&&q.back().val<a[i])q.pop_back(); q.push_back(point(i,a[i])); } printf("%d ",q.front().val); for(register int i=k+1;i<=n;i++) { while(!q.empty()&&q.front().tim+k-1<i)q.pop_front(); while(!q.empty()&&q.back().val<a[i])q.pop_back(); q.push_back(point(i,a[i])); printf("%d ",q.front().val); } } int main() { n=read();k=read(); for(register int i=1;i<=n;i++)a[i]=read(); solve1(); solve2(); return 0; }
st表：
OwO
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1000005; const int INF=(~0u>>1); inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } int n,k; int Log[N],f_min[N][23],f_max[N][23]; inline int query_min(int l,int r) { int m=Log[r-l+1]; return min(f_min[l][m],f_min[r-(1<<m)+1][m]); } inline int query_max(int l,int r) { int m=Log[r-l+1]; return max(f_max[l][m],f_max[r-(1<<m)+1][m]); } int main() { n=read();k=read(); Log[0]=-1; for(register int i=1;i<=n;i++)Log[i]=Log[(i>>1)]+1; for(register int i=1;i<=n;i++) for(register int j=0;j<23;j++)f_min[i][j]=INF; for(register int i=1;i<=n;i++)f_min[i][0]=f_max[i][0]=read(); for(register int j=1;j<23;j++) for(register int i=1;i+(1<<(j-1))-1<=n;i++) { f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<(j-1))][j-1]); f_max[i][j]=max(f_max[i][j-1],f_max[i+(1<<(j-1))][j-1]); } for(register int i=1;i+k-1<=n;i++)printf("%d ",query_min(i,i+k-1)); printf("\n"); for(register int i=1;i+k-1<=n;i++)printf("%d ",query_max(i,i+k-1)); return 0; }
还试了下线段树…T掉一个点Orz
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1000005; const int INF=(~0u>>1); inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return s*f; } int n,k; int t1[N<<2],t2[N<<2],a[N]; #define lson (node<<1) #define rson (node<<1|1) inline void push_up(int node) { t1[node]=max(t1[lson],t1[rson]); t2[node]=min(t2[lson],t2[rson]); } inline void build(int node,int l,int r) { if(l==r) { t1[node]=t2[node]=a[l]; return; } int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); push_up(node); } inline int query_max(int node,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return t1[node]; int mid=(l+r)>>1; int res=-INF; if(mid>=ql)res=max(res,query_max(lson,l,mid,ql,qr)); if(mid+1<=qr)res=max(res,query_max(rson,mid+1,r,ql,qr)); return res; } inline int query_min(int node,int l,int r,int ql,int qr) { if(ql<=l&&r<=qr)return t2[node]; int mid=(l+r)>>1; int res=INF; if(mid>=ql)res=min(res,query_min(lson,l,mid,ql,qr)); if(mid+1<=qr)res=min(res,query_min(rson,mid+1,r,ql,qr)); return res; } #undef lson #undef rson int main() { n=read();k=read(); for(register int i=1;i<=n;i++)a[i]=read(); build(1,1,n); for(register int i=1;i+k-1<=n;i++)printf("%d ",query_min(1,1,n,i,i+k-1)); printf("\n"); for(register int i=1;i+k-1<=n;i++)printf("%d ",query_max(1,1,n,i,i+k-1)); return 0; }