$2000000\times22\times4Byte=167.84668MB$,题目空间限制是 $125MB$。
by ran_qwq @ 2023-09-25 21:50:39
直接对j这一维滚动就好了吧,因为对于 ``query(1,i-1)`` 一类的直接维护前缀min就好了;对于 ``query(i-m,i-1)`` 一类的,其实里面的 ``k=lg[r-l+1]`` 对于所有此类的 $i$ 是定值,因为区间长度恒为 $m$,所以 ``st`` 表也只要算到这一维就行了
by diandian2020 @ 2023-09-25 21:58:08
刚写的:
```cpp
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e6+9;
int n,m,k;
int loggg[N],st[2][N];
void buildST(){
for(int i=2;i<=n;i++) loggg[i]=loggg[i>>1]+1;
k=loggg[m];
for(int j=1;j<=k;j++)
for(int i=1;i+(1<<j)<=n;i++)
st[j&1][i]=min(st[j-1&1][i],st[j-1&1][i+(1<<j-1)]);
}
int query(int l,int r){
return min(st[k&1][l],st[k&1][r-(1<<k)+1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&st[0][i]);
for(int i=1,mn=1e9;i<=m;i++){
if(i==1) puts("0");
else printf("%d\n",mn);
mn=min(mn,st[0][i]);
}//前一半直接统计前缀min
buildST();//后一半st表
for(int i=m+1;i<=n;i++) printf("%d\n",query(i-m,i-1));
return 0;
}
```
by diandian2020 @ 2023-09-25 22:04:45
@[diandian2020](/user/477032) 不对这不是也会MLE呀,你只也应该减不了你的空间复杂度
by HEzzz @ 2023-09-29 21:49:08
@[fengruijun](/user/475532) 我空间复杂度是线性,怎么MLE了,不懂
by diandian2020 @ 2023-09-30 14:50:51
@[diandian2020](/user/477032) 啊空间复杂度不是你数组的大小吗
by HEzzz @ 2023-09-30 15:25:15
@[fengruijun](/user/475532) 您好好看看吧
by diandian2020 @ 2023-09-30 17:24:38
@[diandian2020](/user/477032) 哦是我脑子短路了
by HEzzz @ 2023-09-30 18:23:08