线段树区间操作
——集合运算
题目大意：给出集合的几个运算,并，交，亦或，差。集合初始为空，给出操作序列，输出最终区间。
思路：集合是有区间给出的，所以用线段树。对应操作：
U [a,b] 将 区间[a,b]置为1
I[a,b] 将区间[0，a-1]，[b + 1,65536]置为0
D[a,b] 将区间[a,b]置为0
C[a,b] 将区间[0，a-1]，[b + 1,65536]置为0
然后将区间[a,b]取反
S[a,b] 将区间[a,b]取反
此题的特殊之处在于每次给定的区间是连续的1。这样操作起来就方便了很多
至于区间的开还是闭，只要将每个数字转化) [ ] ( 四个状态即可
提交情况：re， tl， ce， wa， ac
原因：
1. 区间是从0开始的，不是1
2. 区间整体取反也可用延时标记
3. 注意（2，2）这种情况
4. 将一个节点置为0或1时，亦或标记应清零
收获：对于线段树来说，只要是区间整体的信息就可以用延时标记
AC code：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef int I64;
typedef unsigned int uI64;
typedef double real;
const double LE = log(2.0);
const uI64 Binary[32] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648};
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define ms(a, b) memset(a, b, sizeof(a))
#define fup(i, a, b) for(i = a; i < b; ++ i)
#define fdn(i, a, b) for(i = a; i > b; -- i)
#define inf 210000000
I64 gcd(I64 a, I64 b){ return b ? gcd(b, a % b) : a;}
I64 lcm(I64 a, I64 b){ return a / gcd(a, b) * b; }
/*
题目：http://poj.org/problem?id=3225
集合的并，交，亦或，差等操作。由于集合是用区间整体给出的，所以可用线段树加速
区间修改用到了两个延时标记，一个是整体赋值的change，另一个是区间取反的Xor
*/
#define maxn 70000
const char eare[6] = ")[](";
struct interval{
int l, r;
interval(){ l = 0, r = 0; }
interval(int _l, int _r) { l = _l, r = _r; }
void init(int _l, int _r){ l = _l, r = _r; }
interval operator * (const interval &A)const{
return interval(max(A.l, l), min(A.r, r));
}
};
interval eg[maxn];
int flag, sit[maxn * 4];
struct segmentTreeNode{
int lsize, rsize, state;
bool changed, Xor;
segmentTreeNode* son[2];
void init(int _lsize, int _rsize, int _state, bool _changed, segmentTreeNode* sonl, segmentTreeNode* sonr){
lsize = _lsize, rsize = _rsize, state = _state, Xor = changed = _changed, son[0] = sonl, son[1] = sonr;
}
int mid(){ return (lsize + rsize) >> 1; }
};
struct segmentTree{
segmentTreeNode *root, * link;
int ad;
segmentTree(){
ad = 0;
link = new segmentTreeNode[maxn * 16];
}
~segmentTree(){
delete[] link;
}
void built(int l, int r, segmentTreeNode* &rt){
rt = &link[ad ++];
rt->init(l, r, 0, 0, NULL, NULL);
if(l == r) return;
built(l, rt->mid(), rt->son[0]);
built(rt->mid() + 1, r, rt->son[1]);
}
/* 改变区间值 */
void renew(segmentTreeNode* &rt, int sate){
if(rt == NULL || rt->state == sate) return;
rt->changed ^= 1;
rt->Xor = 0;
rt->state = sate;
}
/* 改变亦或延迟标记 */
void rexor(segmentTreeNode* &rt){
if(rt->state != -1){
rt->changed ^= 1;
rt->state ^= 1;
return;
}
rt->Xor ^= 1;
}
/* 延迟标记向下传递 */
void down(segmentTreeNode* &rt){
if(rt == NULL) return;
if(rt->Xor){
rt->Xor = 0;
rexor(rt->son[0]);
rexor(rt->son[1]);
return;
}
if(rt->state == -1) return;
renew(rt->son[0], rt->state);
renew(rt->son[1], rt->state);
rt->state = -1;
rt->changed = 0;
}
/* 将区间l到r置为sate */
void update(int l, int r, int sate, segmentTreeNode* rt){
if(l > r) return;
if(l == rt->lsize && r == rt->rsize){
renew(rt, sate);
return;
}
down(rt);
if(l > rt->mid()) update(l, r, sate, rt->son[1]);
else{
if(r <= rt->mid()) update(l, r, sate, rt->son[0]);
else{
update(l, rt->mid(), sate, rt->son[0]);
update(rt->mid() + 1, r, sate, rt->son[1]);
}
}
if(rt->son[0]->state == rt->son[1]->state){
rt->state = rt->son[0]->state;
}
}
/* 将区间l，r取反 */
void negate(int l, int r, segmentTreeNode* rt){
if(rt == NULL || l > r) return;
if(l == rt->lsize && r == rt->rsize){
rexor(rt);
return;
}
down(rt);
if(l > rt->mid()) negate(l, r, rt->son[1]);
else{
if(r <= rt->mid()) negate(l, r, rt->son[0]);
else{
negate(l, rt->mid(), rt->son[0]);
negate(rt->mid() + 1, r, rt->son[1]);
}
}
if(rt->son[0]->state == rt->son[1]->state){
rt->state = rt->son[0]->state;
}
}
/* 输出区间 */
void out(segmentTreeNode* rt){
if(rt == NULL) return;
if(rt->state != -1){
if(rt->state == 1) {
for(int i = rt->lsize; i <= rt->rsize; ++ i) sit[i] = 1;
}
return;
}
down(rt);
out(rt->son[0]);
out(rt->son[1]);
}
};
const int n = 65536;
int reget(int x, char od){
x *= 4;
if(od == '(') return x + 3;
if(od == ')') return x + 0;
if(od == '[') return x + 1;
if(od == ']') return x + 2;
}
int main(){
char ord[3], l[2], r[2], ch[2];
int x, y;
segmentTree seg;
seg.built(0, (n + 1) * 4, seg.root);
while(~scanf("%1s %1s %d %1s %d %1s", ord, l, &x, ch, &y, r)){
switch(ord[0]){
case 'U' :
x = reget(x, l[0]);
y = reget(y, r[0]);
if(x > y) continue;
seg.update(x, y, 1, seg.root);
break;
case 'I' :
x = reget(x, l[0]);
y = reget(y, r[0]);
if(x > y){
seg.update(0, (n + 1) * 4, 0, seg.root);
continue;
}
seg.update(reget(0, '['), x - 1, 0, seg.root);
seg.update(y + 1, reget(n, ']'), 0, seg.root);
break;
case 'D' :
x = reget(x, l[0]);
y = reget(y, r[0]);
if(x > y) continue;
seg.update(x, y, 0, seg.root);
break;
case 'C' :
x = reget(x, l[0]);
y = reget(y, r[0]);
if(x > y){
seg.update(0, (n + 1) * 4, 0, seg.root);
continue;
}
seg.update(reget(0, '['), x - 1, 0, seg.root);
seg.update(y + 1, reget(n, ']'), 0, seg.root);
seg.negate(x, y, seg.root);
break;
case 'S' :
x = reget(x, l[0]);
y = reget(y, r[0]);
if(x > y) continue;
seg.negate(x, y, seg.root);
break;
}
}
flag = 0;
seg.out(seg.root);
x = -1;
for(int i = 0; i < maxn * 4; ++ i){
if(x == -1 && sit[i] == 1) x = i;
if(sit[i] == 0 && x != -1){
if(flag) printf(" ");
printf("%c%d,%d%c", eare[x % 4], x / 4, (i - 1) / 4, eare[(i - 1) % 4]);
flag = 1;
x = -1;
}
}
if(!flag) printf("empty set\n");
else printf("\n");
return 0;
}