题意
一个集合，初始为空。
请你维护以下 \(3\) 种操作。
- 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中。
- 把 \([l, r]\) 中在集合中出现过的数从集合中删掉。
- 把 \([l, r]\) 中在集合中没有出现过的数添加到集合中，并把 \([l, r]\) 中在集合中出现过的数从集合中删掉。
每次操作后输出集合的 \(mex\)。
\(l, r \le 10 ^ {18}\)
Sol
不难发现，我们可以用一棵动态开点权值线段树维护这个东西。
前两个操作直接区间赋值，第三个操作区间翻转即可。
查询直接在权值线段树上二分。
然后你花不到 \(10min\) 码出了代码。
然后 RE on test14。
你急了，不断地在 MLE 和 RE 中徘徊。
索性花了不到 \(1min\) 码了棵珂朵莉，过了。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <set>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
#define fi first
#define se second
namespace Chtholly {
class Node {
public:
int l, r;
mutable int v;
Node (int _l, int _r, int _v) : l(_l), r(_r), v(_v) {}
bool operator <(const Node &t) const { return l < t.l; }
};
set <Node> Cht;
auto split(int x, int n) {
if (x > n) return Cht.end();
auto it = --Cht.upper_bound(Node(x, 0, 0));
if (it -> l == x) return it;
int l = it -> l, r = it -> r, v = it -> v;
Cht.erase(it), Cht.insert(Node(l, x - 1, v));
return Cht.insert(Node(x, r, v)).fi;
}
void assign1(int l, int r, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
Cht.erase(itl, itr), Cht.insert(Node(l, r, 1));
}
void assign2(int l, int r, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
Cht.erase(itl, itr), Cht.insert(Node(l, r, 0));
}
void revers(int l, int r, int n) {
auto itr = split(r + 1, n), itl = split(l, n);
for (auto it = itl; it != itr; it++)
it -> v ^= 1;
}
int query() {
for (auto it = Cht.begin(); it != Cht.end(); it++)
if (!it -> v) return it -> l;
return -1;
}
}
using namespace Chtholly;
signed main() {
Cht.insert(Node((int)1e18 + 1, (int)1e18 + 1, 0));
Cht.insert(Node(1, 1e18, 0));
int q = read(), n = (int)1e18 + 1;
while (q--) {
int op = read(), l = read(), r = read();
if (op == 1) assign1(l, r, n);
if (op == 2) assign2(l, r, n);
if (op == 3) revers(l, r, n);
write(query()), puts("");
}
return 0;
}