题解 P1440 【求m区间内的最小值】

写了两种，单调队列和ST都写了 但是 ST加读优输优还是T了两个点，可是按时间复杂度nlogn貌似能过= =欢迎大神吐槽 先来单调队列： ```cpp #include<cstdio> int n,m,a[2000000],q[2000000],l=1,r=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { printf("%d\n",a[q[l]]);//输出队首 if(i-q[l]+1>m && l<=r) l++;//查看队首是否在区间内，不在的话出队列 while(a[i]<a[q[r]] && l<=r) r--;//进队比较，把比它大的都踢出去 q[++r]=i; } } ``` ST倍增，欢迎大神解答如何AC，别想复制黏贴，贴了也会T两个点，自己写吧： ```cpp #include<cstdio> #include<cmath> #include<iostream> using namespace std; int n,m,a[2000010],f[25][2000010]; int read() { int x=0; char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar(); return x; } int write(int x) { if(x>=10)write(x/10); putchar(x%10+'0'); ``` }//读优输优加不加随便，加了也是T = = ```cpp int main() { n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) f[0][i]=a[i];//初始化 for(int i=1;i<=log(n)/log(2);i++) for(int j=0;j<=n-(1<<i)+1;j++)//别忘了从0开始 { if(f[i-1][j]==0) f[i][j]=f[i-1][j+(1<<(i-1))]; else if(f[i-1][j+(1<<(i-1))]==0) f[i][j]=f[i-1][j];//注意除非两个都是0，不要取0，不然第一个会挂 else f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);//倍增转移 } for(int i=1;i<=n;i++) { int l=max(0,i-m),r=i-1;//max记得加，不然RE int k=log(r-l+1)/log(2); int ans=min(f[k][l],f[k][r-(1<<k)+1]); write(ans); putchar('\n'); } return 0; } 再次求助一下各路大神，有没有ST过的？ ```