【SDOI2008】校门外的区间
Time Limit: 10 Sec
Memory Limit: 128 MB
Description
受校门外的树这道经典问题的启发，A君根据基本的离散数学的知识，抽象出5种运算维护集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
5种运算如下：
U T -> S∪T
I T -> S∩T
D T -> S－T
C T -> T－S
S T -> S⊕T
基本集合运算如下：
A∪B {x : x∈A or x∈B}
A∩B {x : x∈A and x∈B}
A－B {x : x∈A and (!x∈B)}
A⊕B (A－B)∪(B－A)
Input
输入共M行。
每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
Output
共一行，即集合S，每个区间后面带一个空格。若S为空则输出"empty set"。
Sample Input
U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
Sample Output
(2,3)
HINT
对于 100% 的数据，0≤a≤b≤65535，1≤M≤70000
标签：线段树
假设只有闭区间，对于每个数，标记其为1还是0。
四种运算对应如下（modify为区间修改，reverse为区间取反）：
$U a,b => modify(a, b, 1)$
$D a,b => modify(a, b, 0)$
$S a,b => reverse(a, b)$
$C a,b => modify(0, a-1, 0), modify(b+1, n, 0), reverse(a, b)$
$I a,b => modify(0, a-1, 0), modify(b+1, n, 0)$
再考虑加入开区间，开区间看作对应$.5$的闭区间。即将(4, 7)看作[4.5, 6.5]。
为了存$.5$的小数，我们将所有区间均乘2，即(4, 7)变为[9, 13]。
又考虑到有0的区间，因而对于所有区间两端点再加2，即(4,7)变为[11, 15]。
最后用线段树维护即可。
对于输出，$O(nlog(n))$扫一遍，找出每个数是1还是0，然后合并区间，双指针跑。
本题细节较多，写的时候得小心。
附上AC代码：
#include <iostream>
#include <cstdio>
#define n (65536*2+1)
using namespace std;
struct node {int val, tag, rev;} tr[n*4+500];
void build(int v, int s, int t) {
tr[v].tag = -1; if (s == t) return; int mid = s+t>>1;
build(v<<1, s, mid), build(v<<1|1, mid+1, t);
}
void downtag(int v, int s, int t) {
if (s == t) {if (~tr[v].tag) tr[v].val = tr[v].tag; tr[v].val ^= tr[v].rev, tr[v].tag = -1, tr[v].rev = 0; return;}
if (~tr[v].tag) tr[v<<1].tag = tr[v<<1|1].tag = tr[v].tag, tr[v<<1].rev = tr[v<<1|1].rev = 0;
tr[v<<1].rev ^= tr[v].rev, tr[v<<1|1].rev ^= tr[v].rev; tr[v].tag = -1, tr[v].rev = 0;
}
int query(int v, int s, int t, int p) {
downtag(v, s, t); if (s == t) return tr[v].val; int mid = s+t>>1;
return p <= mid ? query(v<<1, s, mid, p) : query(v<<1|1, mid+1, t, p);
}
void modify(int v, int s, int t, int l, int r, int x) {
if (s > t) return; downtag(v, s, t);
if (s >= l && t <= r) {tr[v].tag = x; return;}
int mid = s+t>>1;
if (l <= mid) modify(v<<1, s, mid, l, r, x);
if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
}
void reverse(int v, int s, int t, int l, int r) {
if (s > t) return; downtag(v, s, t);
if (s >= l && t <= r) {tr[v].rev ^= 1; return;}
int mid = s+t>>1;
if (l <= mid) reverse(v<<1, s, mid, l, r);
if (r >= mid+1) reverse(v<<1|1, mid+1, t, l, r);
}
int main() {
char opt, lbr, rbr; int l, r; build(1, 1, n);
while (~scanf("%c %c%d,%d%c
", &opt, &lbr, &l, &r, &rbr)) {
l <<= 1, r <<= 1, l = l+(lbr == '(')+2, r = r-(rbr == ')')+2;
if (opt == 'U') modify(1, 1, n, l, r, 1);
if (opt == 'I') modify(1, 1, n, 1, l-1, 0), modify(1, 1, n, r+1, n, 0);
if (opt == 'D') modify(1, 1, n, l, r, 0);
if (opt == 'C') modify(1, 1, n, 1, l-1, 0), modify(1, 1, n, r+1, n, 0), reverse(1, 1, n, l, r);
if (opt == 'S') reverse(1, 1, n, l, r);
}
int st = -1, en = -1; bool flag = false;
for (int i = 1; i <= n; i++) {
if (query(1, 1, n, i)) {
if (st == -1) st = i;
en = i;
} else {
if (~st) {
if (flag) printf(" ");
else flag = true;
printf("%c", (st%2 == 1) ? '(' : '[');
printf("%d,%d", st/2-1, (en+1)/2-1);
printf("%c", (en%2 == 1) ? ')' : ']');
}
st = en = -1;
}
}
if (!flag) printf("empty set");
return 0;
}