POJ 3225
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
刚刚做的时候没有理解,后来才知道(2,3)区间也是可以的,不是一个点,而是区间,因为输入都是整数,所以,(2,3)扩大为(4,6),这样[5,5],就可以来取代(2,3)这种情况
继续写实验报告吧,3周没课了,天天睡懒觉,美好的早上总被我浪费掉,拖出去,树上吊起来吧,课程设计实验报告一大堆,还有一天就要上课了,加油!!
#include<iostream>
using namespace std;
const int MAX=65536<<1;//65535<<1;改成65600<<1就不对了
struct T
{
int col;//表示颜色
int cnt;//表示取反的次数
int l,r,m;
}tree[MAX*3];
struct N
{
int x,y;
}node[MAX];//这里改成node[MAX*2]就不对了
int size=0;
void Build_tree(int root,int l,int r)//创建树
{
tree[root].l=l;
tree[root].r=r;
tree[root].m=(l+r)>>1;
tree[root].cnt=0;
if (l==r)
{
tree[root].col=0;
return;
}
tree[root].col=-1;
Build_tree(root<<1,l,tree[root].m);
Build_tree(root<<1|1,tree[root].m+1,r);
};
void Updata(int root,int l,int r,int k)
{
if(tree[root].l==l&&tree[root].r==r)
{
if(k==-1) tree[root].cnt++;
else
{
tree[root].col=k;
tree[root].cnt=0;
}
return ;
}
if(tree[root].col!=-1)
{
if (tree[root].cnt%2)
tree[root].col=!tree[root].col;
tree[root<<1].col=tree[root<<1|1].col=tree[root].col;
tree[root<<1].cnt=tree[root<<1|1].cnt=tree[root].cnt=0;
tree[root].col=-1;
}
if (tree[root].cnt%2)
{
tree[root<<1].cnt++;
tree[root<<1|1].cnt++;
tree[root].cnt=0;
}
if (r<=tree[root].m)//左子树
Updata(root<<1,l,r,k);
else if (l>tree[root].m)
Updata(root<<1|1,l,r,k);
else
{
Updata(root<<1,l,tree[root].m,k);
Updata(root<<1|1,tree[root].m+1,r,k);
}
}
void Query(int root)
{
if (tree[root].col!=-1)
{
if(tree[root].cnt%2)
tree[root].col=!tree[root].col;
if (tree[root].col)
{
node[size].x=tree[root].l;
node[size++].y=tree[root].r;
}
return ;
}
if(tree[root].cnt%2)
{
tree[root<<1].cnt++;
tree[root<<1|1].cnt++;
tree[root].cnt=0;
}
Query(root<<1);
Query(root<<1|1);
}
int main()
{
Build_tree(1,0,MAX);
char ch[4],ci,cj;
int a,b;
while(scanf("%s %c%d,%d%c",ch,&ci,&a,&b,&cj)!=EOF)
{
a=2*a;
b=2*b;
if (ci=='(')
a+=1;
if (cj==')')
b-=1;//这里[a,b]闭区间
switch(ch[0])
{
case 'U'://[a,b]全部变1(并)
if(a <= b)//过滤空集
Updata(1,a,b,1);
break;
case 'I'://(交)
if(a>0)
Updata(1,0,a-1,0);
Updata(1,b+1,MAX,0);
break;
case 'D'://(S-T)
if(a <= b)//过滤空集
Updata(1,a,b,0);
break;
case 'C':// (T-S)
if(a>0)
Updata(1,0,a-1,0);
Updata(1,b+1,MAX,0);
if(a<=b)//过滤空集
Updata(1,a,b,-1);//取反
break;
case 'S':
if(a<=b)//过滤空集
Updata(1,a,b,-1);//取反
break;
}
}
Query(1);
补充:软件开发 , C++ ,