> 
> #include<iostream>
> #include<algorithm>
> #include<stdio.h>
> #include<memory.h>
> #include<math.h>
> using namespace std;
> const int N=65535;
> 
> struct A{int l,r,f;}t[10*N];
> 
> void build_tree(int ll,int rr,int num)
> {
> 	t[num].l=ll,t[num].r=rr,t[num].f=0;
> 	if(ll==rr) return;
> 	int mid=(ll+rr)/2;
> 	build_tree(ll,mid,2*num);
> 	build_tree(mid+1,rr,2*num+1);
> }
> 
> void inset(int ll,int rr,int num,int tf)
> {
> 	if(t[num].f!=-1&&t[num].l<t[num].r)
> 		t[2*num].f=t[2*num+1].f=t[num].f;
> 	if(t[num].l==ll&&t[num].r==rr&&tf!=2)
> 	{
> 		t[num].f=tf;
> 		return;
> 	}
> 	if(t[num].l==ll&&t[num].r==rr&&t[num].f!=-1&&tf==2)
> 	{
> 		t[num].f=(t[num].f==0)?1:0;
> 		return;
> 	}
> 	int mid=(t[num].l+t[num].r)/2;
> 	if(rr<=mid) inset(ll,rr,2*num,tf);
> 	else if(ll>mid) inset(ll,rr,2*num+1,tf);
> 	else
> 	{
> 		inset(ll,mid,2*num,tf);
> 		inset(mid+1,rr,2*num+1,tf);
> 	}
> 	if(t[2*num].f==t[2*num+1].f)
> 		t[num].f=t[2*num].f;
> 	else t[num].f=-1;
> }
> 
> int a[2*N+1];
> 
> void query(int num)
> {
> 	if(t[num].f!=-1)
> 	{
> 		int i;
> 		for(i=t[num].l;i<=t[num].r;i++)
> 			a[i]=t[num].f;
> 		return;
> 	}
> 	query(2*num);
> 	query(2*num+1);
> }
> int main()
> {
> //	freopen("1.txt","r",stdin);
> 	char x,tl,tr;
> 	int sl,sr,i,j,k,cnt;
> 	build_tree(0,2*N,1);
> 	while(scanf("%c %c%d,%d%c%*c",&x,&tl,&sl,&sr,&tr)!=EOF)
> 	{
> 		if(tl=='[') sl=2*sl;
> 		else sl=2*sl+1;
> 		if(tr==']') sr=2*sr;
> 		else sr=2*sr-1;
> 		switch(x)
> 		{
> 			case 'U':if(sl<=sr) inset(sl,sr,1,1);break;
> 			case 'I':if(sl>0) inset(0,sl-1,1,0); if(sr<2*N) inset(sr+1,2*N,1,0);break;
> 			case 'D':if(sl<=sr) inset(sl,sr,1,0); break;
> 			case 'C':if(sl>0) inset(0,sl-1,1,0); if(sr<2*N) inset(sr+1,2*N,1,0);if(sl<=sr) inset(sl,sr,1,2);break;
> 			case 'S':if(sl<=sr) inset(sl,sr,1,2); break;
> 			default:return 0;
> 		}
> 	}
> 	memset(a,false,sizeof(a));
> 	query(1);
> 	cnt=0;
> 	for(i=0;i<=2*N;i++)
> 	{
> 		while(a[i]==0&&i<=2*N)
> 		{
> 			i++;
> 		}
> 		j=i;
> 		while(a[i]==1&&i<=2*N)
> 		{
> 			i++;
> 		}
> 		k=i-1;
> 		if(i>2*N) break;
> 		if(cnt) printf(" ");
> 		cnt++;
> 		if(j%2==0) printf("[%d",j/2);
> 		else printf("(%d",j/2);
> 		printf(",");
> 		if(k%2==0) printf("%d]",k/2);
> 		else printf("%d)",(k+1)/2);
> 	}
> 	if(cnt==0) printf("empty set");
> 	printf("\n");
> 	return 0;
> }

• Re:囧，我刚才蛋疼用官方数据测您的代码，没有超时，但有个点wa了…… (10) 201101050424 2012-10-11 09:06:31