学步园

题目地址 ： http://poj.org/problem?id=3225

最开始是对左右括号、区间覆盖等状态，都加到线段树里，处理麻烦至极。

写了200+行代码，实在不行了，果断放弃。。。

跑去看了HH大牛的Blog，思路果然新颖，于是套用之~~~~~

                                   对于每个输入的数，乘以2，对于开区间'('、')'，相应的+1或者-1，闭区间则不操作。

                                  于是括号的状态与区间覆盖的状态融合到了一块，并且能够一起操作而不影响正确性

                                  最后查询结果的时候，只需要按照原先处理的方法反过来，判断一下就OK~

WA了几天，终于过了~~~   好囧。。。

错误1： 范围从0到maxn，结果我一直都是在1到maxn区间内更新。。。

错误2： 由于错误1，我多改出来的一个错，也是学的不精吧，三位运算符的 优先级没搞好：

                               把R=(R<<1)+(rq==')') 改成了： R=(R<<1)+(rq==')')?1:0;

                               而上面改过之后的式子其实相当于： R=((R<<1)+(rq==')'))?1:0;

                               正确的方式应该是：   R=(R<<1)+((rq==')')?1:0);

查错查的好苦~~

最后基本上是对着HH大牛的代码改的~~  代码改的都快一样了~~  才发现错误所在~~~

贴上AC代码~~   

PS:   Query与HH大牛不一样~~ 效率上来说更快一些、、 

Update部分一开始自己写，只用了一个Cover，TLE了

不得已参照了HH大牛的方式，多加了个XOR状态，效率果然快了很多。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll (v<<1)
#define rr (v<<1|1)
#define tmid ((r+l)>>1)

using namespace std;

const int maxn=140000;

int cover[maxn<<2],XOR[maxn<<2];
int resl[maxn],resr[maxn],cnt;

void update(char op,int L,int R,int l,int r,int v){
	if(L<=l && r<=R){
		if(op=='U')	
			cover[v]=1,XOR[v]=0;
		else if(op=='D')
			cover[v]=0,XOR[v]=0;
		else if(op=='C' || op=='S')
			XOR[v]^=1;
		return ;
	}
	if(cover[v]!=-1){
		cover[ll]=cover[rr]=cover[v]; 
		XOR[ll]=XOR[rr]=0;
		cover[v]=-1;
	}
	if(XOR[v]){
		XOR[ll]^=1;
		XOR[rr]^=1;
		XOR[v]=0;
	}
//	cout<<l<<" "<<r<<endl;
	if(L<=tmid) update(op,L,R,l,tmid,ll);
	else if(op=='C' || op=='I') cover[ll]=XOR[ll]=0;
	if(R>tmid) update(op,L,R,tmid+1,r,rr);
	else if(op=='C' || op=='I') cover[rr]=XOR[rr]=0;
}

void query(int x,int l,int r,int v){
	x^=XOR[v];
	if(cover[v]==-1){
		query(x,l,tmid,ll);
		query(x,tmid+1,r,rr);
		return;
	}
	if(cover[v]^x==0) return;
	if(cover[v]^x==1){
		resl[cnt]=l,resr[cnt]=r;
		cnt++;
	}
}
void make_res(){
	int cnt1,i;
	cnt=cnt1=0;
	query(0,0,maxn,1);
	for(i=1;i<cnt;i++){
		if(resr[cnt1]+1==resl[i])
			resr[cnt1]=resr[i];
		else{
			cnt1++;
			resl[cnt1]=resl[i];
			resr[cnt1]=resr[i];
		}
	}
	if(cnt)
		for(i=0;i<=cnt1;i++){
			if(i) putchar(' ');
			printf("%c%d,%d%c",resl[i]&1?'(':'[',resl[i]>>1,(resr[i]+1 )>>1,resr[i]&1?')':']'); 
		}
	else printf("empty set");
	puts("");
}

int main(){
	char op,lq,rq;
	int L,R;
	cover[1]=XOR[1]=0;
	while(~scanf("%c %c%d,%d%c\n",&op,&lq,&L,&R,&rq)){
		L=(L<<1)+(lq=='(');
		R=(R<<1)-(rq==')');
	//	printf("%c%d,%d%c\n",L&1?'(':'[',L>>1,(R+1)>>1,R&1?')':']');
		if(L<=R) update(op,L,R,0,maxn,1);
		else if(op=='I' || op=='C')
				cover[1]=XOR[1]=0;
	//	make_res();
	}
	make_res();
	return 0;
}