P1198 [JSOI2008] 最大数

#include<iostream>
#define int long long
using namespace std;

const int N=2e5+10;

int m,d,pre[N],f[N],fid[N],cnt1,cnt2;

//思路是由于后缀最大值单调，新加入一个数
//找到恰好小于它的位置，之后的位置有很多父亲（并查集） 
//让这些父亲指向新的它 
//fid是存父亲点的数组 
//再从父亲点的数组中二分查出来哪些父亲要删除 
//求调玄关 

int find(int x){
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

signed main(){
	cin>>m>>d;
	
	for(int i=1;i<=2e5;i++)f[i]=i;
	
	int t=0;
	
	while(m--){
		char op;cin>>op;
		if(op=='A'){
			int n;cin>>n;int x=(n+t+d)%d;
			int l=0,r=cnt1+1;
			while(l<r){
				int mid=l+r>>1;
				if(pre[find(mid)]<x)r=mid;
				else l=mid+1;
			}
			if(cnt1==0)pre[0]=x;
			pre[++cnt1]=x;
//		l之后都要改
//		从fid中找到l以及之后的
			fid[++cnt2]=cnt1;
			int L=1,R=cnt2;
			while(L<R){
				int mid=L+R>>1;
				if(fid[mid]<=l)L=mid+1;else R=mid;
			} 
			int tt=cnt2;
			for(int i=L;i<=cnt2;i++){
				tt--;f[fid[i]]=cnt1;
			}
			cnt2=tt;
			fid[++cnt2]=cnt1;
		}else{
			int l;cin>>l;
			cout<<pre[find(cnt1-l+1)]<<endl;
			t=pre[find(cnt1-l+1)];
		}
	}
	
	return 0;
}