RP大有问题
不知哪进死循环了
自己生成的数据都很快,而且答案和AC的程序生成的一样
代码如下:

#include<stdio.h>
#include<memory>
#include<string.h>
int z[65536*2*4+32];    //代表线段的状态，1为被覆盖，-1为未被覆盖，0为既有被覆盖的部分又有未被覆盖的部分，需要子线段来确定
void u(int id,int p,int q,int pp,int qq)
{
	if(p==pp&&q==qq)
	{
		z[id]=1;
		return;
	}
	int l,r,mid;
	mid=(p+q)>>1;
	l=(id<<1)+1;
	r=l+1;
	if(z[id])
		z[l]=z[r]=z[id];
	if(qq<=mid)
		u(l,p,mid,pp,qq);
	else if(pp>=mid+1)
		u(r,mid+1,q,pp,qq);
	else
	{
		u(l,p,mid,pp,mid);
		u(r,mid+1,q,mid+1,qq);
	}
	if(z[l]*z[r]==1)
		z[id]=z[l];
	else
		z[id]=0;
}
void f(int id,int p,int q,int pp,int qq)
{
	if(p==pp&&q==qq)
	{
		z[id]=-1;
		return;
	}
	int l,r,mid;
	mid=(p+q)>>1;
	l=(id<<1)+1;
	r=l+1;
	if(z[id])
		z[l]=z[r]=z[id];
	if(qq<=mid)
		f(l,p,mid,pp,qq);
	else if(pp>=mid+1)
		f(r,mid+1,q,pp,qq);
	else
	{
		f(l,p,mid,pp,mid);
		f(r,mid+1,q,mid+1,qq);
	}
	if(z[l]*z[r]==1)
		z[id]=z[l];
	else
		z[id]=0;
}
void tt(int id,int p,int q,int pp,int qq)
{
	if(p==pp&&q==qq)
	{
		z[id]=-z[id];
		if(z[id])
			return;
	}
	int l,r,mid;
	mid=(p+q)>>1;
	l=(id<<1)+1;
	r=l+1;
	if(z[id])
		z[l]=z[r]=z[id];
	if(qq<=mid)
		tt(l,p,mid,pp,qq);
	else if(pp>=mid+1)
		tt(r,mid+1,q,pp,qq);
	else
	{
		tt(l,p,mid,pp,mid);
		tt(r,mid+1,q,mid+1,qq);
	}
	if(z[l]*z[r]==1)
		z[id]=z[l];
	else
		z[id]=0;
}

int ans[65536*2+32];
void out(int id,int p,int q)
{
	if(z[id])
	{
		int i;
		for(i=p;i<=q;i++)
		   ans[i]=z[id];
		return;
	}
	int l,r,mid;
	mid=(p+q)>>1;
	l=(id<<1)+1;
	r=l+1;
	out(l,p,mid);
	out(r,mid+1,q);
}

int main()
{
	int g=65536*2;
	char c,l,r;
	int i,p,q,j;
	bool ok;
	memset(z,0XFF,sizeof(z));
	while(scanf("%c %c%d,%d%c\n",&c,&l,&p,&q,&r)==5)
	{
		p<<=1;
		if(l=='(')
			p++;
		q<<=1;
		if(r==')')
			q--;
		if(c=='U')
		{
			if(p<=q)
			    u(0,0,g,p,q);
		}
		else if(c=='I')
		{
			if(p>0)
			    f(0,0,g,0,p-1);
			if(g>q)
			    f(0,0,g,q+1,g);
		}
		else if(c=='D')
		{
			if(p<=q)
			    f(0,0,g,p,q);
		}
		else if(c=='C')
		{
			if(p<=q)
			{
				if(p>0)
					f(0,0,g,0,p-1);
				if(g>q)
					f(0,0,g,q+1,g);
				tt(0,0,g,p,q);
			}
			else
				z[0]=-1;
		}
		else if(c=='S')
		{
			if(p<=q)
			    tt(0,0,g,p,q);
		}
	}
	out(0,0,g);
	ok=false;
	for(i=0;i<=g;i++)
		if(ans[i]==1)
		{
			for(j=i+1;j<=g;j++)
				if(ans[j]!=1)
					break;
			j--;
			if(ok)
				printf(" ");
			else
				ok=true;
			if(i&1)
				printf("(%d,",i>>1);
			else
				printf("[%d,",i>>1);
			if(j&1)
				printf("%d)",(j+1)>>1);
			else
				printf("%d]",(j+1)>>1);
			i=j;
		}
	if(!ok)
		printf("empty set");
	printf("\n");
	return 0;
}

• Re:严重求救 (26) windy7926778 2007-05-10 12:07:53
• 解决了,不用了,谢谢了哈 (12) windy7926778 2007-05-10 13:10:50
  • 我的代码跟你得差不多啊,你怎么过的 (0) 407811696 2010-10-08 00:44:45