POJ 3225 Help with Intervals（线段树）

题意：区间交、并、减、补

思路：用线段树的叶子节点记录该点是否被区间覆盖，因为有开区间的情况，因此考虑离散，将数值乘以2。

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互换

区间修改容易做，但是加上区间异或就难了。

我们考虑维护这样一棵线段树，如果区段的setv不是-1（初始化时候为-1），则说明该节点所对应的区段内全部的值为setv，如果根节点和子节点的setv值都不为-1，我们只认根节点上面的setv值。然后维护一个xorv值，表示该节点对应区段是否被异或奇数次（异或偶数次和没异或一样，是0）。这个xorv值一定出现在查找时第一次遇到setv值的前面，也就是说，查找时会先遇到有意义的xorv值，再遇到有意义的setv值（有意义是指，xorv=1，或者setv!=-1）。当要修改某个区段或寻找某个区段的过程中，xorv值和setv值会用pushdown不断往下压。明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了。所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记。

输出的时候，我们可以用一个hash数组记录，用一个query将线段树上的值往下压到hash数组里面。

注意几个问题：1.出现0的情况

2.(3,3)这种空集的情况

#include
#include
#define M ((L+R)>>1)
#define ls (o<<1)
#define rs (o<<1|1)
#define lson ls,L,M
#define rson rs,M+1,R
const int maxn=66666*2;
bool hash[maxn],empty=1,flag=0;
int n,yl,yr,v,setv[maxn*4],xorv[maxn*4],a,b,low=0,high;
char op,left,right;
void fxor(int o) {if(setv[o]>=0) setv[o]^=1; else xorv[o]^=1;}
void pushdown(int o)
{
	if(setv[o]>=0) {setv[ls]=setv[rs]=setv[o];xorv[ls]=xorv[rs]=0;setv[o]=-1;}
	if(xorv[o])
	{
		fxor(ls);
		fxor(rs);
		xorv[o]=0;
	}
}
void setupdate(int o,int L,int R)
{
	if(yl<=L && R<=yr) {xorv[o]=0;setv[o]=v;return;}
	pushdown(o);
	if(yl<=M) setupdate(lson);
	if(M=0)
	{
		if(setv[o]) for(int i=L;i<=R;++i) hash[i]=1;//将信息压倒hash里面去
		return;
	}
	pushdown(o);
	if(yl<=M) query(lson);
	if(M=maxn) break;
		empty=0;
		if(flag) printf(" ");
		flag=1;
		if(low&1) printf("(");
		else printf("[");
		printf("%d,%d",(low/2)-1,(high-1)/2);
		if(high&1) printf(")");
		else printf("]");
		low=high+1;
	}
	if(empty) printf("empty set");
	puts("");
}
int main()
{
	init();
	read();
	print();
	return 0;
}