st表但是全RE求救

kowalski @ 2017-10-30 08:04:24

#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
long long f[2000020][35];
int a[2000020];
int st(int n){
    int x=log(n)/log(2);
    for(int i=0;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=i-m;int r=i-1;
        if(l<0)l=0;
        if(l==0)l=1;
        printf("%d\n",rmqmin(l,r));
    }
    return 0;
}

by xw001 @ 2017-10-30 10:10:15

@kowalski f数组，定义太大了，f[2000000][21]就够了

by kowalski @ 2017-11-05 15:58:33

@xw001 改了继续RP求破

by kowalski @ 2017-11-05 15:58:45

@kowalski RE

by xw001 @ 2017-11-05 16:11:59

@kowalski 先贴我的80分TLE代码

#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:18:55

@kowalski 找到问题了QAQ，你这个查询有问题啊。下面是我改了你的代码的结果：

#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:20:26

@xw001 但是呢这不是正解。。。本来你看看200w就应该知道不是用RMQ，不管是空间还是时间（空间实际上还是超了的，不知道为什么没显示超空间。。。）。本题正解是单调队列。。。

by kowalski @ 2017-11-05 16:27:50

@xw001 哦谢谢一直没注意最下面居然是那里错了……