是谁贴上了倍增的标签，果断TLE2点啊==

睿屿青衫 @ 2017-10-17 20:22:54

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 3000000
using namespace std;
int n,m,minn[maxn][24];
void init()
{
    for(int j=1;(1<<j)<=n;++j)
     for(int i=1;i+(1<<j)-1<=n;++i)
      minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
}
int rmq_min(int l,int r)
{
    int k=log2(r-l+1);
    return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
     cin>>minn[i][0];
    init();
    for(int i=1;i<=n;++i)
     {
         if(i==1) printf("0\n");
          else if(i<=m) printf("%d\n",rmq_min(1,i-1));
           else printf("%d\n",rmq_min(i-m,i-1));
     }
    return 0;
}
80不嫌弃拿走

by 青衫白叙 @ 2017-10-17 20:32:03

。。明明是单调队列。。

by 青衫白叙 @ 2017-10-17 20:32:27

还有。。知道时限卡还用cin。。。

by 青衫白叙 @ 2017-10-17 20:34:56

要的话，我可以顺手放下一个快读。。保证不T。。。@睿屿青衫丶

by 睿屿青衫 @ 2017-10-17 20:42:20

@青衫白叙 我擦 我一直用ios::sync_with_stdio(false) 今天被教练刚了一顿 然而成习惯了没换回来

by 青衫白叙 @ 2017-10-17 20:45:09

@睿屿青衫丶 习惯顺手打好快读。。。

by 睿屿青衫 @ 2017-10-17 20:52:52

@青衫白叙 我本来背了一个快读，结果让他坑了不知道多少遍，果断扔下了

by xw001 @ 2017-10-30 10:11:32

@青衫白叙 说好的保证不T的呢？？还是T了两个点啊

#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-10-30 10:14:10

提交列表里面就没哪个是用RMQ过的！！

by 青衫白叙 @ 2017-10-30 10:35:24

@xw001 我的快读。。。。

by xw001 @ 2017-10-30 10:51:32

@青衫白叙 你不是说好的送给我的吗，我就用用呗。。。