P1198 [JSOI2008] 最大数

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int m,d;
const int maxn=1e6+10;
const int maxx=25;
int a[maxn];
int f[maxn][maxx];
int lg[maxn];
int cmp=0;
	int ans=0;
int q(int l,int r){
	int j=lg[r-l+1];
	return max(f[l][j],f[r+1-(1<<j)][j]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>d;
//	q();

	while(m--){
		char s;
		cin>>s;
		if(s=='A'){
			cmp++;
			int x;
			cin>>x;
			a[cmp]=(x+ans)%d;
			int j=0;
			while((1<<j)<=cmp){
				int i=cmp-(1<<j)+1;
				if(j==0)f[i][j]=a[cmp];
				else f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
				j++;	
			}
		}
		if(s=='Q'){
			int x;
			cin>>x;
			ans=q(cmp-x+1,cmp);
			cout<<ans<<'\n';
		}
	}
	return 0;
}