很好用的线性求变换区间最值的方法，比线段树快
用到了优先队列的算法
据说能用STL双向队列解但我不会QAQ
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int n,k; int ans,l,r,a,b; int num[1000007]; int q[1000007],q2[1000007]; int p[1000007]; void maxl(){ //max int head=1; int tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&q[tail]<=num[i]) tail--; q[++tail]=num[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } cout<<endl; } void minl(){ //min int head=1; int tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&q[tail]>=num[i]) tail--; q[++tail]=num[i]; p[tail]=i; while(p[head]<=i-k) head++; if(i>=k) printf("%d ",q[head]); } cout<<endl; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&num[i]); minl(); maxl(); return 0; }