2017.9.15 最大數maxnumber 思考記錄

數論太難了，就水水結構

都是splay的基本操作，維護最大值和size即可

插入時直接找右子樹

查找時往左邊找

資料結構不對拍就不要交（奇奇怪怪的錯誤）

注意：區間合并時要考慮自己這個節點

碼：

#include<iostream>
#include<cstdio>
using namespace std;
#define N  200005 
int sz[N],ch[N][3],maxx[N],max1[N],fu[N],ans,rt,m,P,n,i,cnt;
char str[55];
void up(int o)
{
	sz[o]=sz[ch[o][0]]+sz[ch[o][1]]+1;
	maxx[o]=max(max(maxx[ch[o][0]],maxx[ch[o][1]]),max1[o]);	
}
void set(int o,int wh,int t)
{
	ch[o][wh]=t;
	fu[t]=o;
	up(o);	
}
int getwh(int o)
{
	return ch[fu[o]][1]==o;
}
void rotate(int o)
{
	int fa=fu[o],ye=fu[fu[o]];
	int wh=getwh(o);
	set(fa,wh,ch[o][wh^1]);
	set(o,wh^1,fa);
	fu[o]=ye;
	if(ye!=0)
	ch[ye][ch[ye][1]==fa]=o;	
}
void splay(int o,int tar)
{
for(;fu[o]!=tar;rotate(o))	
	if(fu[fu[o]]!=tar)
	getwh(o)==getwh(fu[o])?rotate(fu[o]):rotate(o);
	if(tar==0)rt=o;	
}
void ins(int val)
{
	++cnt;
	maxx[cnt]=val;
	max1[cnt]=val;
	sz[cnt]=1;
	int o=rt;
	if(o==0)
	{
		rt=cnt;
		return ;
	}
	while(ch[o][1])o=ch[o][1];
	set(o,1,cnt);	
	splay(cnt,0);
}
int wen(int k)
{
	int o=rt;
	ans=0;
	while(o)
	{
		if(sz[ch[o][1]]+1==k)
		{
			ans=max(ans,max(maxx[ch[o][1]],max1[o]));
			break;
		}else
		if(sz[ch[o][1]]+1<k)
		{
			ans=max(max(maxx[ch[o][1]],max1[o]),ans);
	    k-=sz[ch[o][1]]+1;
	    o=ch[o][0];
		}else o=ch[o][1];
	}
	splay(o,0);
	return ans;
}
int main()
{
scanf("%d%d",&m,&P);
for(i=1;i<=m;i++)
{
	scanf("%s",str);
	scanf("%d",&n);
	if(str[0]=='A')
	{
		ins((1ll*n+1ll*ans)%P);
	}else
	{
		printf("%d\n",wen(n));		
	}
}		
}