@[kowalski](/space/show?uid=20631) f数组，定义太大了，f[2000000][21]就够了
by xw001 @ 2017-10-30 10:10:15
@[xw001](/space/show?uid=15044) 改了继续RP求破
by kowalski @ 2017-11-05 15:58:33
@[kowalski](/space/show?uid=20631) RE
by kowalski @ 2017-11-05 15:58:45
@[kowalski](/space/show?uid=20631) **先贴我的80分TLE代码**
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
int f[2000001][21],n,a[2000001],m;
void rmq_init(){
for(int i = 1;i <= n; i++)
f[i][0] = a[i];
for(int j = 1;(1<<j) <= n; j++)
for(int i = 1;i+(1<<j)-1<=n;i++)
f[i][j] = min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int rmq_min(int L,int R){
int k =0;
while((1<<(k+1)) <= R-L+1) k++;
return min(f[L][k],f[R-(1<<k)+1][k]);
}
inline int read(){
int x=0,f=1;
char ch = getchar();
while(ch>'9' || ch<'0'){
if(ch == '-')
f=-1;
ch = getchar();
}
while(ch<='9' && ch>='0'){
x=x*10+ch-'0';
ch = getchar();
}
return x*f;
}
int main(){
n = read(),m=read();
for(int i =1 ;i <= n; i++)
a[i] = read();
rmq_init();
for(int i =1;i<=n;i++){
int l ;
if(i == 1)
l =0;
else if(i-m<1)
l = 1;
else
l = i-m;
printf("%d\n",rmq_min(l,i-1));
}
}
```
by xw001 @ 2017-11-05 16:11:59
@[kowalski](/space/show?uid=20631) 找到问题了QAQ，你这个查询有问题啊。下面是我改了你的代码的结果：
```cpp
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int f[2000020][25];
int a[2000020];
int st(int n){
int x=log(n)/log(2);
for(int i=1;i<=n;i++)f[i][0]=a[i];
for(int j=1;j<=x;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int rmqmin(int l,int r){
int d=log(r-l+1)/log(2);
return min(f[l][d],f[r-(1<<d)+1][d]);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
st(n);
for(int i=1;i<=n;i++){
int l ;
if(i == 1)
l =0;
else if(i-m<1)
l = 1;
else
l = i-m;
printf("%d\n",rmqmin(l,i-1));
}
return 0;
}
```
by xw001 @ 2017-11-05 16:18:55
@[xw001](/space/show?uid=15044) 但是呢这不是正解。。。本来你看看200w就应该知道不是用RMQ，不管是空间还是时间（空间实际上还是超了的，不知道为什么没显示超空间。。。）。本题正解是单调队列。。。
by xw001 @ 2017-11-05 16:20:26
@[xw001](/space/show?uid=15044) 哦谢谢一直没注意最下面居然是那里错了……
by kowalski @ 2017-11-05 16:27:50