记录编号	60803	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]项链工厂	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.163 s
提交时间	2013-05-30 14:07:26	内存使用	32.80 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEN=500999;
class SEG{
public:
	int l,r;
	int lchild,rchild;
	int sum;//不同颜色的区间数目
	int lcover,rcover;
	int carry;//0就是不同色,否则就是本段共同的颜色
	void build(int x,int y);
	void merge(void);
	void update(int c);
	void pushdown(void);
	int inqcolor(int x);
	void paint(int x,int y,int c);
	int getsum(int x,int y);
};
int color[SIZEN]={0};
SEG tree[SIZEN*2];
SEG& root=tree[0];
int tot;
#define lson tree[lchild]
#define rson tree[rchild]
void SEG::build(int x,int y){
	l=x,r=y;
	carry=0;
	if(x==y){
		lchild=rchild=-1;
		lcover=rcover=color[x];
		sum=1;
	}
	else{
		int mid=(x+y)>>1;
		lchild=++tot;
		lson.build(x,mid);
		rchild=++tot;
		rson.build(mid+1,y);
		merge();
	}
}
void SEG::merge(void){
	lcover=lson.lcover;
	rcover=rson.rcover;
	sum=lson.sum+rson.sum;
	if(lson.rcover==rson.lcover) sum--;
}
void SEG::update(int c){//染成上面传下来的的c
	sum=1;
	lcover=rcover=c;
	carry=c;
}
void SEG::pushdown(void){//单纯的下传标记
	if(!carry||l==r) return;
	lson.update(carry);
	rson.update(carry);
	carry=0;
}
int SEG::inqcolor(int x){//查询位置x的颜色
	if(r<x||l>x) return 0;//不包含
	if(l==r&&l==x)	return lcover;
	if(carry){
		pushdown();
		merge();
	}
	return lson.inqcolor(x)+rson.inqcolor(x);//两个之中一个是0另一个是值
}
void SEG::paint(int x,int y,int c){//[x,y]染成c
	if(r<x||l>y) return;
	if(l>=x&&r<=y){//包含
		sum=1;
		lcover=rcover=c;
		carry=c;
		pushdown();
		return;
	}
	pushdown();
	lson.paint(x,y,c);
	rson.paint(x,y,c);
	merge();
}
int SEG::getsum(int x,int y){//查询[x,y]中的段数
	if(r<x||l>y) return 0;
	if(l>=x&&r<=y) return sum;
	int mid=(l+r)>>1;
	pushdown();
	merge();
	int temp=lson.getsum(x,y)+rson.getsum(x,y);
	if(mid<x||mid>=y){
		return temp;
	}
	else{
		if(lson.rcover==rson.lcover) return temp-1;
		else return temp;
	}
}
int n,numc,q;
bool flipped;//是否被翻转
int tran;//顺时针移动位数
void offset(int &x){
	x-=tran;
	if(flipped)	x=n+2-x;
	while(x<=0) x+=n;
	while(x>n) x-=n;
}
void init(void){
	tot=0;
	tran=0,flipped=false;
	scanf("%d%d",&n,&numc);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&color[i]);
	root.build(1,n);
}
int section(int x,int y){
	int temp;
	if(x<=y) temp=root.getsum(x,y);
	else temp=root.getsum(x,n)+root.getsum(1,y);
	if((x>y||(x==1&&y==n))&&temp>1&&root.lcover==root.rcover) temp--;
	return temp;
}
void swap(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}
void MOD(int &x){
	while(x>n) x-=n;
	while(x<=0) x+=n;
}
int req;
void work(void){
	scanf("%d",&req);
	char str[5]={0};
	int i,temp,a,b;
	int c;
	int c1,c2;
	for(i=1;i<=req;i++){
		scanf("%s",str);
		if(str[0]=='R'){//旋转
			scanf("%d",&temp);
			tran+=temp;
			MOD(tran);
		}
		else if(str[0]=='F'){//翻转
			tran*=-1;
			flipped=!flipped;
			MOD(tran);
		}
		else if(str[0]=='S'){//调换
			scanf("%d%d",&a,&b);
			offset(a),offset(b);
			if(flipped) swap(a,b);
			c1=root.inqcolor(a),c2=root.inqcolor(b);
			root.paint(a,a,c2);
			root.paint(b,b,c1);
		}
		else if(str[0]=='P'){//染色
			scanf("%d%d%d",&a,&b,&c);
			offset(a),offset(b);
			if(flipped) swap(a,b);
			if(a<=b) root.paint(a,b,c);
			else{
				root.paint(a,n,c);
				root.paint(1,b,c);
			}
		}
		else if(str[0]=='C'&&str[1]=='S'){//查询区间
			scanf("%d%d",&a,&b);
			offset(a),offset(b);
			if(flipped) swap(a,b);
			printf("%d\n",section(a,b));
		}
		else if(str[0]=='C'){//查询全段
			printf("%d\n",section(1,n));
		}

	}
}
int main(){
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	init();
	work();
	return 0;
}