CF817F MEX Queries

题意

一个集合，初始为空。

请你维护以下 \(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;
}