题目
略
题解
直接套黄学长模板。
Orz
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000000
#define n (65536 * 2 + 1)
char ch[5];
int read() {
int x = 0, f = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '(')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
if (ch == ')')
f = 1;
return x * 2 - f;
}
struct seg {
int l, r, val, tag, rev;
} t[4 * n];
void build(int k, int l, int r) {
t[k].l = l;
t[k].r = r;
t[k].tag = -1;
if (l == r)
return;
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
}
void pushdown(int k) {
int tag = t[k].tag, rev = t[k].rev;
t[k].tag = -1;
t[k].rev = 0;
if (t[k].l == t[k].r) {
if (tag != -1)
t[k].val = tag;
t[k].val ^= rev;
return;
}
if (tag != -1) {
t[k << 1].tag = t[k << 1 | 1].tag = tag;
t[k << 1].rev = t[k << 1 | 1].rev = 0;
}
t[k << 1].rev ^= rev;
t[k << 1 | 1].rev ^= rev;
}
int query(int k, int x) {
pushdown(k);
int l = t[k].l, r = t[k].r;
if (l == r)
return t[k].val;
int mid = (l + r) >> 1;
if (x <= mid)
return query(k << 1, x);
else
return query(k << 1 | 1, x);
}
void modify(int k, int x, int y, int val) {
if (y < x)
return;
pushdown(k);
int l = t[k].l, r = t[k].r;
if (l == x && r == y) {
if (val == -1)
t[k].rev ^= 1;
else
t[k].tag = val;
return;
}
int mid = (l + r) >> 1;
if (y <= mid)
modify(k << 1, x, y, val);
else if (x > mid)
modify(k << 1 | 1, x, y, val);
else {
modify(k << 1, x, mid, val);
modify(k << 1 | 1, mid + 1, y, val);
}
}
void rever(int k, int x, int y) { modify(k, x, y, -1); }
int main() {
build(1, 1, n);
while (scanf("%s", ch) != EOF) {
int a = read(), b = read();
a += 2;
b += 2;
switch (ch[0]) {
case 'U':
modify(1, a, b, 1);
break;
case 'I':
modify(1, 1, a - 1, 0);
modify(1, b + 1, n, 0);
break;
case 'D':
modify(1, a, b, 0);
break;
case 'C':
modify(1, 1, a - 1, 0);
modify(1, b + 1, n, 0);
rever(1, a, b);
break;
case 'S':
rever(1, a, b);
break;
}
}
int start = -1, last = -1, flag = 0;
for (int i = 1; i <= n; i++) {
if (query(1, i)) {
if (start == -1)
start = i;
last = i;
} else {
if (start != -1) {
if (flag)
printf(" ");
else
flag = 1;
if (start & 1)
printf("(");
else
printf("[");
printf("%d", start / 2 - 1);
printf(",");
printf("%d", (last + 1) / 2 - 1);
if (last & 1)
printf(")");
else
printf("]");
}
last = start = -1;
}
}
if (!flag)
printf("empty set");
return 0;
}