#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e5;
LL len=0,mylog[N+5],f[N+5][25];
void init(){
	for(LL i=1;i<=N;i++){
		mylog[i]=log2(i);
	}
}
void insert(LL x){
	f[++len][0]=x;
	for(LL j=1;j<=20;j++){
		if(len-(1<<j)>=0)
			f[len][j]=max(f[len][j-1],f[len-(1<<(j-1))][j-1]);
	}
}
LL query(LL l,LL r){
	LL k=mylog[r-l+1];
	return max(f[l+(1<<k)-1][k],f[r][k]);
}
int main(){
	init();
	LL n,mod,last=0;
	scanf("%lld%lld",&n,&mod);
	for(LL i=1;i<=n;i++){
		char op[10];LL x;
		scanf("%s",op+1);
		if(op[1]=='Q'){
			scanf("%lld",&x);
			printf("%lld\n",last=query(len-x+1,len));
		}
		if(op[1]=='A'){
			scanf("%lld",&x);
			insert((x+last)%mod);
		}
	}
	return 0;
}

强制在线，不超过m使用线段树维护。也可以使用rmq简化查询使编码更简化高效。

1、线段树

#include<stdio.h>
#include<iostream>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mid (l+r)/2
#define debug(x) cout<<#x<<" :"<<x<<endl 
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

int t,x,y,z,n,m;
int d;
char s[10];
int pos[maxn],val[maxn];
int q[maxn];
int ans[maxn];
struct node{
    int tr[maxn<<2],lazy[maxn<<2];
    void pushup(int rt){//由儿子更新到当前父亲节点
        tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);
    }
    void pushdown(int l,int r,int rt){
    }
    void build(int l,int r,int rt){
        if(l==r){
            return ;
        }
        build(lson);
        build(rson);
        pushup(rt);
    }
    void update(int L,int R,int l,int r,int rt,int val){//更新
        if(L<=l&&r<=R){
        	tr[rt]=val;
        	return ;
		}
		if(L<=mid){
			update(L,R,l,mid,rt<<1,val);
		}
		if(R>mid){
			update(L,R,mid+1,r,rt<<1|1,val);
		}
        pushup(rt);
    }
    int query(int L,int R,int l,int r,int rt){
        if(L<=l&&r<=R){
  
        	return tr[rt];
		}
		int ans=-0x3f3f3f3f;
		if(L<=mid){
			ans=max(ans,query(L,R,l,mid,rt<<1));
		}
		if(R>mid){
			ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
		}
		pushup(rt);
		return ans;
    }
    void init(){
        for(int i=1;i<=maxn*4-1;++i){
            lazy[i]=0;
        }
    }
}sgt;
int main(){


    while(~scanf("%d %d",&m,&d)){
		t=0;
		int sum=0;//almost m number 
		for(int i=1;i<=m;++i){
			scanf("%s %d",s,&n);
			if(s[0]=='A'){//add a value to the end
				n=(n+t)%d;
				if(n<0){
					n+=d;
					n%=d;
				}
				sum++;
				sgt.update(sum,sum,1,m,1,n);
			}
			else if(s[0]=='Q'){

				int ans=sgt.query(sum-n+1,sum,1,m,1);
				printf("%d\n",ans);
				t=ans; 
			}
		}
	}
  
    return 0;
}