題意：區(qū)間交、并、減、補(bǔ)
思路：用線段樹(shù)的葉子節(jié)點(diǎn)記錄該點(diǎn)是否被區(qū)間覆蓋，因?yàn)橛虚_(kāi)區(qū)間的情況，因此考慮離散，將數(shù)值乘以2。
U:把區(qū)間[l,r]覆蓋成1
I:把[-∞,l)(r,∞]覆蓋成0
D:把區(qū)間[l,r]覆蓋成0
C:把[-∞,l)(r,∞]覆蓋成0 , 且[l,r]區(qū)間0/1互換
S:[l,r]區(qū)間0/1互換
區(qū)間修改容易做，但是加上區(qū)間異或就難了。
我們考慮維護(hù)這樣一棵線段樹(shù)，如果區(qū)段的setv不是-1(初始化時(shí)候?yàn)?1)，則說(shuō)明該節(jié)點(diǎn)所對(duì)應(yīng)的區(qū)段內(nèi)全部的值為setv，如果根節(jié)點(diǎn)和子節(jié)點(diǎn)的setv值都不為-1，我們只認(rèn)根節(jié)點(diǎn)上面的setv值。然后維護(hù)一個(gè)xorv值，表示該節(jié)點(diǎn)對(duì)應(yīng)區(qū)段是否被異或奇數(shù)次(異或偶數(shù)次和沒(méi)異或一樣，是0)。這個(gè)xorv值一定出現(xiàn)在查找時(shí)第一次遇到setv值的前面，也就是說(shuō)，查找時(shí)會(huì)先遇到有意義的xorv值，再遇到有意義的setv值(有意義是指，xorv=1，或者setv!=-1)。當(dāng)要修改某個(gè)區(qū)段或?qū)ふ夷硞€(gè)區(qū)段的過(guò)程中，xorv值和setv值會(huì)用pushdown不斷往下壓。明顯我們可以知道這個(gè)性質(zhì):當(dāng)一個(gè)區(qū)間被覆蓋后,不管之前有沒(méi)有異或標(biāo)記都沒(méi)有意義了。所以當(dāng)一個(gè)節(jié)點(diǎn)得到覆蓋標(biāo)記時(shí)把異或標(biāo)記清空托福答案
而當(dāng)一個(gè)節(jié)點(diǎn)得到異或標(biāo)記的時(shí)候,先判斷覆蓋標(biāo)記,如果是0或1,直接改變一下覆蓋標(biāo)記,不然的話改變異或標(biāo)記托福改分
輸出的時(shí)候，我們可以用一個(gè)hash數(shù)組記錄，用一個(gè)query將線段樹(shù)上的值往下壓到hash數(shù)組里面。
注意幾個(gè)問(wèn)題：1.出現(xiàn)0的情況
2.(3,3)這種空集的情況
#include<cstdio>
#include<cstring>
#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<yr) setupdate(rson);
}
void xorupdate(int o,int L,int R)
{
if(yl<=L && R<=yr){fxor(o);return;}
pushdown(o);
if(yl<=M) xorupdate(lson);
if(M<yr) xorupdate(rson);
}
void query(int o,int L,int R)
{
if(setv[o]>=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<yr) query(rson);
}
void init()
{
memset(setv,-1,sizeof(setv));
memset(hash,0,sizeof(hash));
xorv[1]=setv[1]=0;
}
void read()
{
while(~scanf("%c %c%d,%d%c ",&op,&left,&a,&b,&right))
{
a=(a+1)*2,b=(b+1)*2;
if(left=='(') ++a; if(right==')') --b;
if(op=='U')
{
v=1,yl=a,yr=b;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='I')
{
v=0,yl=1,yr=a-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=b+1,yr=maxn-1;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='D')
{
v=0,yl=a,yr=b;
if(yl<=yr) setupdate(1,1,maxn-1);
}
else if(op=='C')
{
v=0,yl=1,yr=a-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=b+1,yr=maxn-1;
if(yl<=yr) setupdate(1,1,maxn-1);
yl=a,yr=b;
if(yl<=yr) xorupdate(1,1,maxn-1);
}
else if(op=='S')
{
yl=a,yr=b;
if(yl<=yr) xorupdate(1,1,maxn-1);
}
}
}
void print()
{
yl=1,yr=maxn-1;
query(1,1,maxn-1);
while(low<maxn)
{
while(!hash[low] && low<maxn) ++low;
high=low+1;
while(hash[high] && high<maxn) ++high;
--high;
if(low>=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;
}