题目地址 题意：你有5种操作，分别为U（并集操作）、I（交集操作）、D（相减操作）、C（反向相减操作）、S（异或操作），让你求出n次操作之后的集合分别是多少 思路：最初为全0，就代表空集，然后对于5种操作的结果就是：
U:把区间[l,r]覆盖成1 I:把[-∞,l)(r,∞]覆盖成0 D:把区间[l,r]覆盖成0 C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换 S:[l,r]区间0/1互换
对于开区间和闭区间通过用再开两倍区间来做，偶数为闭区间，奇数为开区间（其他的就不难了）
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #define N 132010 #define LL __int64 #define inf 0x3f3f3f3f #define lson l,mid,ans<<1 #define rson mid+1,r,ans<<1|1 #define getMid (l+r)>>1 #define movel ans<<1 #define mover ans<<1|1 using namespace std; const LL mod = 1e9 + 7; const double eps = 1e-9; struct node { LL sum; int xors; }sum[N << 2];//线段树主体 bool flag[N]; struct Segment__Tree { int x, y; void getxor(int ans) { if (sum[ans].sum != -1) { sum[ans].sum ^= 1; } else { sum[ans].xors ^= 1; } } void pushUp(int ans) { if (sum[movel].sum == sum[mover].sum) { sum[ans].sum = sum[movel].sum; } else { sum[ans].sum = -1; } } void pushDown(int ans) { if (sum[ans].sum != -1) { sum[movel].sum = sum[mover].sum = sum[ans].sum; sum[movel].xors = sum[mover].xors = 0; } if (sum[ans].xors) { getxor(movel); getxor(mover); sum[ans].xors = 0; } } void build() { memset(sum, 0, sizeof(sum)); memset(flag, false, sizeof(flag)); } void solve(int l, int r, int ans) { if (sum[ans].sum == 1) { for (int i = l; i <= r; i++) { flag[i] = true; } return; } else if (!sum[ans].sum || l == r) { return; } pushDown(ans); int mid = getMid; solve(lson); solve(rson); } void updata(int l, int r, int ans, int s) { if (l >= x&&r <= y) { if (s == -1) { if (sum[ans].sum != -1) { sum[ans].sum ^= 1; } else sum[ans].xors ^= 1; } else { sum[ans].sum = s; sum[ans].xors = 0; } return; } if (sum[ans].sum != -1 && sum[ans].sum == s) { return; } pushDown(ans); int mid = getMid; if (mid<x) { updata(rson, s); } else if (mid >= y) { updata(lson, s); } else { updata(lson, s); updata(rson, s); } pushUp(ans); } }; int main() { Segment__Tree tree; tree.build(); char s, l, r, c; while (~scanf(" %c %c%d,%d%c", &s, &l, &tree.x, &tree.y, &r)) { tree.x *= 2; tree.y *= 2; if (s == 'U') { if (l == '(') { tree.x++; } if (r == ')') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 1); } else if (s == 'D') { if (l == '(') { tree.x++; } if (r == ')') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 0); } else if (s == 'I') { int a = tree.x; int b = tree.y; tree.x = b; tree.y = N - 1; if (r == ']') { tree.x++; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 0); tree.y = a; tree.x = 0; if (l == '[') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 0); } else if (s == 'C') { int a = tree.x; int b = tree.y; if (l == '(') { tree.x++; } if (r == ')') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, -1); tree.x = b; tree.y = N - 1; if (r == ']') { tree.x++; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 0); tree.y = a; tree.x = 0; if (l == '[') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, 0); } else { if (l == '(') { tree.x++; } if (r == ')') { tree.y--; } if (tree.x > tree.y) { continue; } tree.updata(0, N - 1, 1, -1); } } tree.solve(0, N - 1, 1); int kk = 0; int cnt = -1, ans; for (int i = 0; i <= N; i++) { if (flag[i]) { if (cnt == -1) { cnt = i; } ans = i; } else if (cnt != -1) { if (kk) printf(" "); printf("%c%d,%d%c", cnt & 1 ? '(' : '[', cnt >> 1, (ans + 1) >> 1, ans & 1 ? ')' : ']'); cnt = -1; kk = 1; } } if (!kk) printf("empty set"); puts(""); return 0; }