集合

Description

对于实数集合，定义以下操作：

Union：A∪B = {x | x∈A or x∈B}

Intersection：A∩B = {x | x∈A and x∈B}

Relative complementation：A–B = {x | x∈A but not x∈B}

Symmetric difference ：A⊕B = (A - B) ∪(B - A)

令当前的主集合为S，给定集合T ，以下是集合处理的简单表示：

U T ←S = S∪T

I T ←S = S∩T

D T ←S = S - T

C T ←S = T - S

S T ←S = S⊕T

假设S一开始为空集，对于给定指令，求出最终的S 集合。

Input Format

若干行，每行一条指令，格式如上。

T集合的模式为(a,b),(a,b],[a,b)或[a,b]

a b均为整数，以文件结束结尾。

数据保证a<=b，其中集合为[a,b]且a=b时请视为该集合里只含一个元素。

Output Format

在一行中用尽量少的区间描述集合S，格式同输入格式，按左端点从小到大输出，每个区间后跟一个空格，详见样例。

保证最终S不为空集

Sample Input

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
U (4,5]

Sample Output

(2,3) (4,5]

Hint

对于40%的数据，不超过1000条指令

对于100%的数据，不超过65536条指令，0<=a<=b<65536

保证指令及答案合法。

分析：

　　实际上就是一个可以维护区间内1的个数的线段树。

　　这几种操作都可以分解成两种基本操作：区间赋值和区间取反。

　　S∪T ：将区间T赋值为1

　　S∩T ：将区间0～T.left和区间T.right～INF赋值为0

　　S - T ：将区间T赋值为0

　　T - S ：将区间0～T.left和区间T.right～INF赋值为0，对区间T取反

　　S⊕T ：对区间T取反

　　开闭区间可以看成0.5来维护，把数值都乘以2就好了。

　　关键在于处理好两个lazy-tag的关系。

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 int n, q, i, al, ar, ak, ai, len;
  5 int s[800000], lz[800000], rt[800000], x1, x2, x[3], p;
  6 char act[10], read[100];
  7 int ql, qr;
  8 
  9 #define MID (l + r >> 1)
 10 #define up(o) (s[o] = s[o << 1] + s[o << 1 | 1])
 11 
 12 void build (int x, int l, int r)
 13 {
 14     if (l != r) build (x << 1, l, MID), build (x << 1 | 1, MID + 1, r);
 15 }
 16 
 17 void down (int x, int l, int r)
 18 {
 19     if (lz[x] != -1)
 20     {
 21         s[x << 1] = (MID - l + 1) * lz[x];
 22         lz[x << 1] = lz[x], rt[x << 1] = 0;
 23         s[x << 1 | 1] = (r - MID) * lz[x];
 24         lz[x << 1 | 1] = lz[x], rt[x << 1 | 1] = 0;
 25         lz[x] = -1;
 26     }
 27     if (rt[x])
 28     {
 29         rt[x << 1] = !rt[x << 1];
 30         s[x << 1] = MID - l + 1 - s[x << 1];
 31         rt[x << 1 | 1] = !rt[x << 1 | 1];
 32         s[x << 1 | 1] = r - MID - s[x << 1 | 1];
 33         rt[x] = 0;
 34     }
 35 }
 36 
 37 void modify (int x, int l, int r)
 38 {
 39     if (l > ar || r < al) return;
 40     if (l >= al && r <= ar)
 41     {
 42         s[x] = (r - l + 1) * ak;
 43         lz[x] = ak; rt[x] = 0; return;
 44     }
 45     down (x, l, r);
 46     if (al <= MID) modify (x << 1, l, MID);
 47     if (ar > MID) modify (x << 1 | 1, MID + 1, r);
 48     l != r ? up (x) : 0;
 49 }
 50 
 51 void rotate (int x, int l, int r)
 52 {
 53     if (l >= al && r <= ar)
 54     {
 55         s[x] = r - l + 1 - s[x];
 56         rt[x] = !rt[x]; return;
 57     }
 58     down (x, l, r);
 59     if (al <= MID) rotate (x << 1, l, MID);
 60     if (ar > MID) rotate (x << 1 | 1, MID + 1, r);
 61     l != r ? up (x) : 0;
 62 }
 63 
 64 void search (int x, int l, int r)
 65 {
 66     if (l == r)
 67     {
 68         if (s[x])
 69         {
 70             if (l > qr) ql = l;
 71             qr = l + 1;
 72         }else
 73         {
 74             if (l == qr)
 75             {
 76                 qr--;
 77                 printf (ql % 2 ? "(" : "[");
 78                 printf ("%d,%d", ql / 2, qr / 2 + qr % 2);
 79                 printf (qr % 2 ? ") " : "] ");
 80             }
 81         }
 82     }else
 83     {
 84         down (x, l, r);
 85         search (x << 1, l, MID);
 86         search (x << 1 | 1, MID + 1, r);
 87     }
 88 }
 89 
 90 int main ()
 91 {
 92     build (1, 0, 150000);
 93     while (~scanf ("%s", act))
 94     {
 95         scanf ("%s", read);
 96         len = strlen (read);
 97         i = 1, p = 0;
 98         x[0] = x[1] = 0;
 99         while (i < len)
100         {
101             if (read[i] >= '0' && read[i] <= '9')
102                 x[p] = x[p] * 10 + read[i] - '0';
103             else p++;
104             i++;
105         }
106         x1 = x[0] * 2 + (read[0] == '(');
107         x2 = x[1] * 2 - (read[len - 1] == ')');
108         switch (act[0])
109         {
110             case 'U':
111                 al = x1, ar = x2, ak = 1;
112                 if (al <= ar) modify (1, 0, 150000);
113             break;
114             case 'I':
115                 al = 0, ar = x1 - 1, ak = 0;
116                 if (al <= ar) modify (1, 0, 150000);
117                 al = x2 + 1, ar = 150000, ak = 0;
118                 if (al <= ar) modify (1, 0, 150000);
119             break;
120             case 'D':
121                 al = x1, ar = x2, ak = 0;
122                 if (al <= ar) modify (1, 0, 150000);
123             break;
124             case 'C':
125                 al = 0, ar = x1 - 1, ak = 0;
126                 if (al <= ar) modify (1, 0, 150000);
127                 al = x2 + 1, ar = 150000, ak = 0;
128                 if (al <= ar) modify (1, 0, 150000);
129                 al = x1, ar = x2;
130                 if (al <= ar) rotate (1, 0, 150000);
131             break;
132             case 'S':
133                 al = x1, ar = x2;
134                 if (al <= ar) rotate (1, 0, 150000);
135             break;
136         }
137     }
138     ql = qr = -1;
139     search (1, 0, 150000);
140 }