记录编号	313616	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]项链工厂	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.425 s
提交时间	2016-10-01 15:54:51	内存使用	16.03 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=500010;
int n,q,c[N],l[N],r[N],s[N],root;
int cl[N],cr[N],num[N];//左端颜色，右端颜色，颜色个数 
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
inline void update(int x){
	s[x]=s[l[x]]+s[r[x]]+1;
	num[x]=num[l[x]]+num[r[x]]+1;
	if (r[x]&&cl[r[x]]==c[x]) num[x]--;
	if (l[x]&&cr[l[x]]==c[x]) num[x]--;
	cl[x]=(l[x]?cl[l[x]]:c[x]);
	cr[x]=(r[x]?cr[r[x]]:c[x]);
}
inline void l_rotate(int &x){
	int y=r[x];
	r[x]=l[y];l[y]=x;
	update(x);update(y);
	x=y;
}
inline void r_rotate(int &x){
	int y=l[x];
	l[x]=r[y];r[y]=x;
	update(x);update(y);
	x=y;
}
bool tag[N];//翻转标记
int p[N];//染色标记 
inline void pushdown(int x){
	if (tag[x]){
		tag[l[x]]^=1;
		tag[r[x]]^=1;
		swap(l[l[x]],r[l[x]]);
		swap(l[r[x]],r[r[x]]);
		swap(cl[l[x]],cr[l[x]]);
		swap(cl[r[x]],cr[r[x]]);
		tag[x]=0;
	}
	if (p[x]<=1000){
		p[l[x]]=p[r[x]]=p[x];
		num[l[x]]=num[r[x]]=1;num[0]=0;
		cl[l[x]]=cr[l[x]]=cl[r[x]]=cr[r[x]]=c[l[x]]=c[r[x]]=p[x];
		p[x]=1001;
	}
}
void splay(int &x,int k){
	pushdown(x);
	int i=s[l[x]]+1;
	if (i==k) return;
	if (k<i) splay(l[x],k),r_rotate(x);
		else splay(r[x],k-i),l_rotate(x);
}
int build(int L,int R){
	if (L>R) return 0;
	int mid=(L+R)/2;
	tag[mid]=0;
	p[mid]=1001;
	l[mid]=build(L,mid-1);
	r[mid]=build(mid+1,R);
	update(mid);
	return mid;
}
inline void Paint(int L,int R,int C){
	splay(root,L);
	splay(root,R+2);
	int x=r[l[root]];
	p[x]=c[x]=cl[x]=cr[x]=C;num[x]=1;
	update(l[root]);
	update(root);
}
inline void paint(int L,int R,int C){
	if (L<=R) Paint(L,R,C);
		else{Paint(1,R,C);Paint(L,n,C);}
}
inline void flip(){
	splay(root,2);
	splay(root,n+2);
	int x=r[l[root]];
	tag[x]^=1;
	swap(l[x],r[x]);
	swap(cl[x],cr[x]);
	update(l[root]);
	update(root);
}
inline void swap(){
	int i=read(),j=read(),ci,cj;
	if (i>j) swap(i,j);
	splay(root,i);
	splay(root,j+2);
	int x=r[l[root]];
	ci=cl[x];cj=cr[x];
	Paint(i,i,cj);
	Paint(j,j,ci);
}
inline void rotate(){
	int k=read();k%=n;
	splay(root,n-k+1);
	splay(root,n+2);
	int x=r[l[root]];
	r[l[root]]=0;
	update(l[root]);
	update(root);
	splay(root,1);
	splay(root,2);
	r[l[root]]=x;
	update(l[root]);
	update(root);
}
inline void CS(){
	int L=read(),R=read();
	if (L<=R){
		splay(root,L);
		splay(root,R+2);
		printf("%d\n",num[r[l[root]]]);
	}
	else{
		splay(root,1);
		splay(root,R+2);
		int x=r[l[root]],ans=num[x],c1=cl[x];
		splay(root,L);
		splay(root,n+2);
		x=r[l[root]];ans+=num[x];
		if (c1==cr[x]) ans--;
		printf("%d\n",ans);
	}
}
inline void C(){
	splay(root,1);
	splay(root,n+2);
	int x=r[l[root]],ans=num[x];
	if (cl[x]==cr[x]) ans--;
	if (!ans) ans++;
	printf("%d\n",ans);
}
void bianli(int x,int C){
	if (!x) return;
	pushdown(x);
	bianli(l[x],C+1);
	for (int i=C;i;i--) putchar('\t');
	printf("c:%d num:%d cl:%d cr:%d\n",c[x],num[x],cl[x],cr[x]);
	bianli(r[x],C+1);
}
int main()
{
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	n=read();read();
	for (int i=2;i<=n+1;i++) c[i]=read();
	root=build(1,n+2);
	q=read();
	while (q--){
		char s[10];
		scanf("%s",s);
		if (s[0]=='R') rotate();else
		if (s[0]=='F') flip();else
		if (s[0]=='S') swap();else
		if (s[0]=='P'){
			int l=read(),r=read(),c=read();
			paint(l,r,c);
		}else
		if (s[1]=='S') CS();
			else C();
	}
	return 0;
}