洛谷 P1198 [JSOI2008]最大数——单调栈/线段树

先上一波题目 https://www.luogu.org/problem/P1198

题目要求维护后缀最大值以及在数列的最后面添加一个数

这道题呢我们有两种做法

1.单调栈

因为只需要维护后缀最大值而我们每次插入都是在最后面添加一个数所以我们可以维护一个单调栈

栈底到栈顶逐渐增大因为如果一个数他的位置在你的前面且他比你小那么他便不会对前面位置的最大值产生影响可以直接省略

我们在查询的时候只需要二分一下答案找到比查询位置后的最接近查询位置的数的值就是答案了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=200007;
long long  read(){
    long long ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
char c;
int stk[M],top=0;
int n,cnt=0;
long long mod,s[M],T=0,x;
int main(){
    n=read(); mod=read();
    for(int i=1;i<=n;i++){
        c=getchar();  
        while(c!='Q'&&c!='A') c=getchar();
        x=read();
        if(c=='Q'){
            x=cnt-x+1;
            long long l=1,r=top;
            while(l<r){
                int mid=(l+r)>>1; 
                if(stk[mid]>=x) r=mid;
                else l=mid+1;
            }
            T=s[r];
            printf("%lld\n",T);
        }
        else{
            cnt++;
            x=(x+T)%mod;
            x=(x+mod)%mod; 
            while(top&&s[top]<=x) top--;
            s[++top]=x; stk[top]=cnt;
        }
    }
    return 0;
}

View Code

2.线段树

线段树就很明显了设计的操作有单点插入区间求最大值

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=400007;
long long  read(){
    long long ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
char c;
int n,cnt=0;
long long mod,T=0,now,s[M*2];
void up(int x){s[x]=max(s[x<<1],s[x<<1^1]);}
void insert(int x,int l,int r){
    if(l==r){
        s[x]=now;
        return ;
    }
    int mid=(l+r)>>1;
    if(cnt<=mid) insert(x<<1,l,mid);
    else insert(x<<1^1,mid+1,r);
    up(x);
}
long long pmx(int x,int l,int r){
    if(now<=l&&r<=cnt) return s[x];
    int mid=(l+r)>>1;
    long long ans=-2147483647;
    if(now<=mid) ans=max(ans,pmx(x<<1,l,mid));
    if(cnt>mid)  ans=max(ans,pmx(x<<1^1,mid+1,r));
    return ans;
}
int main(){
    n=read(); mod=read();
    for(int i=1;i<=n;i++){
        c=getchar();
        while(c!='Q'&&c!='A') c=getchar();
        now=read();
        if(c=='Q'){
            now=cnt-now+1;
            T=pmx(1,1,n);
            printf("%lld\n",T);
        }
        else{
            cnt++;
            now=(now+T)%mod;
            insert(1,1,n);
        }
    }
    return 0;
}

View Code

洛谷 P1198 [JSOI2008]最大数——单调栈/线段树

相关推荐