[線分樹マーク]BZOJ 3226[Sdoi 2008]学外の区間

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline int read()
{
    int x=0,f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='(')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	if(ch==')')f=1;
    return x*2-f;
}

struct Seg{
	int M,TH;
	int H[600005],R[600005];
	inline void Build(int n){
		for (M=1;M<n+2;M<<=1,TH++);
		for (int i=1;i<M;i++)
			H[i]=-1;
	}
	inline void pushdown(int x){
		if (R[x])
		{
			R[x<<1]^=1; if (H[x<<1]!=-1) H[x<<1]^=1;
			R[x<<1|1]^=1; if (H[x<<1|1]!=-1) H[x<<1|1]^=1;
			R[x]^=1;
		}
		if (H[x]!=-1)
		{
			H[x<<1]=H[x<<1|1]=H[x];
			H[x]=-1;
		}
	}
	inline void Pushdown(int rt){
		int p;
		for (int i=TH;i;i--)
			pushdown(rt>>i);
	}
	inline void Reverse(int s,int t){
		if (s>t) return;
		for (Pushdown(s+=M-1),Pushdown(t+=M+1);s^t^1;s>>=1,t>>=1)
		{
			if (~s&1) { R[s^1]^=1; if (H[s^1]!=-1) H[s^1]^=1; }
			if ( t&1) { R[t^1]^=1; if (H[t^1]!=-1) H[t^1]^=1; }
		}
	}
	inline void Change(int s,int t,int c){
		if (s>t) return;
		for (Pushdown(s+=M-1),Pushdown(t+=M+1);s^t^1;s>>=1,t>>=1)
		{
			if (~s&1) H[s^1]=c,R[s^1]=0;
			if ( t&1) H[t^1]=c,R[t^1]=0;
		}
	}
	inline int Query(int s){
		Pushdown(s+=M);
		return H[s];
	}
}SEG;

const int n=(65536*2+1);
//const int n=(5*2+1);

int main()
{
	int a,b;
	char ch[3];
	char type, flag_l, flag_r,flag=0;
	freopen("t.in","r",stdin);
	freopen("t.out","w",stdout);
	SEG.Build(n);
	while (~scanf("%s",ch))
    {
	    a=read(); b=read();
        a+=2; b+=2;
		switch(ch[0])
		{
			case 'U':
				SEG.Change(a,b,1);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				break;
			case 'I':
				SEG.Change(1,a-1,0);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				SEG.Change(b+1,n,0);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				break;
			case 'D':
				SEG.Change(a,b,0);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				break;
			case 'C':
				SEG.Change(1,a-1,0);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				SEG.Change(b+1,n,0);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				SEG.Reverse(a,b);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				break;
			case 'S':
				SEG.Reverse(a,b);
//				for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
				break;
		}
	}
	int start=-1,last=-1;
	flag=0;
//	for(int i=1;i<=n;i++) printf("%d ",SEG.Query(i)); printf("
");
	for(int i=1;i<=n;i++)
		if(SEG.Query(i))
		{
			if(start==-1) start=i;
			last=i;
		}
		else 
		{
			if(start!=-1)
			{
				if(flag)printf(" ");
				else flag=1;
				if(start&1)printf("(");
				else printf("[");
				printf("%d",start/2-1);
				printf(",");
				printf("%d",(last+1)/2-1);
				if(last&1)printf(")");
				else printf("]");
			}
			last=start=-1;
		}
	if(!flag) 
		printf("empty set
");
	return 0;
}