P4392 [BOI2007]Sound 静音问题

链接：Miku

这道题本质上还是个st表，只要两个st表，然后对于每一个点，查询他开始的

长度为m的去年的最大值，最小值之差就可以了。

然而这个题还有个坑点，太大了，直接写会MLE，我们重新读一下题，题目说了区间是M。

那我们最多开到log2（m）就可以了，再大也用不到啊（这个小优化让它变成了绿题）

然后就可以AC了。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cmath>
using namespace std;
int st[1000001][15];
int st2[1000001][15];
int x,y;
int n,m,c;
int f;
int main(){
    cin>>n>>m>>c;
    int k=log2(m);
    for(int i=1;i<=n;++i){
        scanf("%d",&st[i][0]);
        st2[i][0]=st[i][0];
    }
    for(int i=1;i<=k;++i){
        for(int j=1;j+(1<<i)-1<=n;++j)
            st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    }
    for(int i=1;i<=22;++i){
        for(int j=1;j+(1<<i)-1<=n;++j)
            st2[j][i]=min(st2[j][i-1],st2[j+(1<<(i-1))][i-1]);
    }
    for(int x=1;x<=n-m+1;++x){
        int y=x+m-1;
        int u=max(st[x][k],st[y-(1<<k)+1][k])-min(st2[x][k],st2[y-(1<<k)+1][k]);
        if(u<=c){
            cout<<x<<endl;
            f=1;
        }
    }
    if(!f)
    cout<<"NONE";
        return 0;
}

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论