#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;
}

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