BZOJ3226【SDOI2008】校门外的区间 <线段树>

Problem

【SDOI2008】校门外的区间

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

受校门外的树这道经典问题的启发，$A$君根据基本的离散数学的知识，抽象出$5$种运算维护集合$S$($S$初始为空)并最终输出$S$。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
$5$种运算如下：

编号	表示格式	数学表示
$1$	$U\;\;T$	$S\cup T$
$2$	$I\;\;T$	$S\cap T$
$3$	$D\;\;T$	$S-T$
$4$	$C\;\;T$	$S+T$
$5$	$S\;\;T$	$S\otimes T$

基本集合运算如下：

运算	结果
$A\cup B$	$\lbrace x\mid x\in A\mid\mid x\in B\rbrace$
$A\cap B$	$\lbrace x\mid x\in A\;\;\&\&\;\;x\in B\rbrace$
$A-B$	$\lbrace x\mid x\in A\;\;\&\&\;\;x\notin B\rbrace$
$A\otimes B$	$(A-B)\cup(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\le a\le b\le 65535$，$1\le M\le 70000$

标签：线段树

Solution

假设只有闭区间，对于每个数，标记其为$1$还是$0$。
四种运算对应如下（$modify$为区间修改，$reverse$为区间取反）：

• $U$ $a,b\Rightarrow modify(a, b, 1)$
• $D$ $a,b\Rightarrow modify(a, b, 0)$
• $S$ $a,b\Rightarrow reverse(a, b)$
• $C$ $a,b\Rightarrow modify(0, a-1, 0), modify(b+1, n, 0), reverse(a, b)$
• $I$ $a,b\Rightarrow 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(n\log(n))$扫一遍，找出每个数是$1$还是$0$，然后合并区间，双指针跑。
本题细节较多，写的时候得小心。

Code

#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\n", &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;
}