先上一波题目 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;
}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;
}