记录编号	265779	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]项链工厂	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	7.168 s
提交时间	2016-06-04 10:58:37	内存使用	17.45 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=500010;
int ch[maxn][2],fa[maxn],sz[maxn],flip[maxn],mark[maxn];
int key[maxn],tot[maxn],L[maxn],R[maxn],rt;
int n,Q,l,r,d,c;
char op[10];
void Push_up(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
	L[x]=ch[x][0]?L[ch[x][0]]:key[x];
	R[x]=ch[x][1]?R[ch[x][1]]:key[x];
	tot[x]=tot[ch[x][0]]+tot[ch[x][1]]+1;
	if(ch[x][0]&&R[ch[x][0]]==key[x])tot[x]-=1;
	if(ch[x][1]&&key[x]==L[ch[x][1]])tot[x]-=1;
}
 
void Flip(int x){
	if(!x)return;
	swap(ch[x][0],ch[x][1]);
	swap(L[x],R[x]);
	flip[x]^=1;
}
 
void Mark(int x,int d){
	if(!x)return;
	key[x]=L[x]=R[x]=d;
	tot[x]=1;mark[x]=d;	
}
 
void Push_down(int x){
	if(mark[x]!=-1){
		Mark(ch[x][0],mark[x]);
		Mark(ch[x][1],mark[x]);
		mark[x]=-1;
	}
	if(flip[x]){
		Flip(ch[x][0]);
		Flip(ch[x][1]);
		flip[x]=0;
	}
}
 
void Rotate(int x){
	int y=fa[x],g=fa[y],c=ch[y][1]==x;
	ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;
	ch[x][c^1]=y;fa[y]=x;fa[x]=g;
	if(g)ch[g][ch[g][1]==y]=x;
	Push_up(y);
}
 
void Splay(int x,int g=0){
	for(int y;(y=fa[x])!=g;Rotate(x))
		if(fa[y]!=g)	
			Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
	Push_up(x);		
	if(!g)rt=x;	
}
 
int Build(int x,int l,int r){
	if(l>r)return 0;
	int mid=(l+r)>>1;
	ch[mid][0]=Build(mid,l,mid-1);
	if(mid!=1&&mid!=n+2)	
		scanf("%d",&key[mid]);	
	ch[mid][1]=Build(mid,mid+1,r);
	sz[mid]=1;mark[mid]=-1;
	fa[mid]=x;Push_up(mid);
	return mid;
}
 
int Get_ID(int k){
	int p=rt;
	while(true){
		Push_down(p);
		if(sz[ch[p][0]]+1==k)break;
		if(sz[ch[p][0]]+1<k)k-=sz[ch[p][0]]+1,p=ch[p][1];
		else p=ch[p][0];	
	}
	return p;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
#endif
	scanf("%d%d",&n,&c);
	rt=Build(0,1,n+2);
	scanf("%d",&Q);
	while(Q--){
		scanf("%s",op);
		if(op[0]=='R'){
			scanf("%d",&d);d%=n;
			if(d==0)continue;
			Splay(Get_ID(n-d+1));
			Splay(Get_ID(n+2),rt);
			int tmp=ch[ch[rt][1]][0];
			ch[ch[rt][1]][0]=0;
			Splay(Get_ID(1));
			Splay(Get_ID(2),rt);
			ch[ch[rt][1]][0]=tmp;
			fa[tmp]=ch[rt][1];
		}
		else if(op[0]=='F'){
			Splay(Get_ID(2));
			Splay(Get_ID(n+2),rt);
			Flip(ch[ch[rt][1]][0]);
		}
		else if(op[0]=='S'){
			scanf("%d%d",&l,&r);
			if(l>r)swap(l,r);
			if(l==r)continue;
			Splay(Get_ID(l+1));
			Splay(Get_ID(r+1),rt);
			swap(key[rt],key[ch[rt][1]]);
		}
		else if(op[0]=='P'){
			scanf("%d%d%d",&l,&r,&d);
			if(l<=r){
				Splay(Get_ID(l));
				Splay(Get_ID(r+2),rt);
				Mark(ch[ch[rt][1]][0],d);
			}
			else{
				Splay(Get_ID(l));
				Splay(Get_ID(n+2),rt);
				Mark(ch[ch[rt][1]][0],d);
				Splay(Get_ID(1));
				Splay(Get_ID(r+2),rt);
				Mark(ch[ch[rt][1]][0],d);
			}
		}
		else if(op[0]=='C'&&op[1]!='S'){
			Splay(Get_ID(1));
			Splay(Get_ID(n+2),rt);
			if(L[ch[ch[rt][1]][0]]==R[ch[ch[rt][1]][0]]&&tot[ch[ch[rt][1]][0]]>1)
				printf("%d\n",tot[ch[ch[rt][1]][0]]-1);
			else
				printf("%d\n",tot[ch[ch[rt][1]][0]]);
		}
		else if(op[0]=='C'&&op[1]=='S'){
			scanf("%d%d",&l,&r);
			if(l<=r){
				Splay(Get_ID(l));
				Splay(Get_ID(r+2),rt);
				printf("%d\n",tot[ch[ch[rt][1]][0]]);
			}
			else{
				int ans=0;
				Splay(Get_ID(l));
				Splay(Get_ID(n+2),rt);
				ans+=tot[ch[ch[rt][1]][0]];
				Splay(Get_ID(1));
				Splay(Get_ID(r+2),rt);
				ans+=tot[ch[ch[rt][1]][0]];
				Splay(Get_ID(1));
				Splay(Get_ID(n+2),rt);
				if(L[ch[ch[rt][1]][0]]==R[ch[ch[rt][1]][0]])
					ans-=1;
				printf("%d\n",ans);	
			}	
		}
	}	
	return 0;
}