[BOJ] 16910 mex와 쿼리

[문제 링크](https://www.acmicpc.net/problem/16910)

문제 요약

다음과 같은 세 쿼리를 처리해야 합니다.

1. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다.

2. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다.

3. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다.

각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다.

문제 풀이

일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상쇄되고, 3번 쿼리끼리 서로 상쇄됩니다. 더해 3번 쿼리는 1번/2번 쿼리의 Lazy를 뒤집습니다. 더 자세하게 설명해서, 한 구간 전체에 쿼리가 연속적으로 적용된다면 Lazy는 다음과 같이 변화합니다.

• 1번 쿼리가 적용될 예정인 배열에 1번 쿼리가 들어오면 무시됩니다. 2번 쿼리가 적용되면 2번 쿼리로 덮어씌워집니다. 3번 쿼리가 적용되어도 2번 쿼리로 바뀝니다.

• 2번 쿼리는 1번 쿼리와 정확히 반대입니다.

• 3번 쿼리가 적용될 예정인 배열에 1번/2번 쿼리가 들어오면 그 쿼리로 덮어씌워집니다. 3번 쿼리가 다시 들어오면, Lazy는 상쇄되어 사라지고 아무것도 할 필요가 없습니다.

만약 수의 개수를 계속 관리해 줄 수 있다면, $$ 시간에 mex를 구해줄 수 있습니다. 세그먼트 트리의 루트부터 보면서 담당하는 구간 중 왼쪽이 가득 차 있다면(구간 길이와 켜져있는 수 개수가 일치한다면) 오른쪽으로, 아니라면 왼쪽으로 내려가면 됩니다. 마지막으로 도달한 리프 노드가 정답입니다.

코드

#include <bits/stdc++.h>
#include <random>
#include <cassert>
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;

const int MOD = 10007;
const ll LMOD = 998244353LL;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;

using namespace std;

struct SegmentTree {
	ll s[1202020], lazy[1202020];

	void push(int nd, int st, int en) {
		if (!lazy[nd]) return;

		if (abs(lazy[nd]) == 1) s[nd] = (lazy[nd] > 0) ? en - st + 1 : 0;
		else s[nd] = en - st + 1 - s[nd];
		if (st == en) {
			lazy[nd] = 0;
			return;
		}
		if (abs(lazy[nd]) == 1) lazy[nd << 1] = lazy[nd << 1 | 1] = lazy[nd];
		else {
			lazy[nd << 1] = (abs(lazy[nd << 1]) == 1) ? -lazy[nd << 1] : 2 - lazy[nd << 1];
			lazy[nd << 1 | 1] = (abs(lazy[nd << 1 | 1]) == 1) ? -lazy[nd << 1 | 1] : 2 - lazy[nd << 1 | 1];
		}
		lazy[nd] = 0;
	}

	void update(int nd, int st, int en, int le, int ri, int val) {
		push(nd, st, en);
		if (le <= st && en <= ri) {
			if (abs(val) == 1) lazy[nd] = val;
			else lazy[nd] = (abs(lazy[nd]) == 1) ? -lazy[nd] : 2 - lazy[nd];
			push(nd, st, en);
			return;
		}
		if (en < le || ri < st) return;
		int mid = st + en >> 1;
		update(nd << 1, st, mid, le, ri, val);
		update(nd << 1 | 1, mid + 1, en, le, ri, val);
		s[nd] = s[nd << 1] + s[nd << 1 | 1];
	}

	ll query(int nd, int st, int en) {
		if (st == en) return st;
		push(nd, st, en);
		int mid = st + en >> 1;
		push(nd << 1, st, mid);
		if (mid - st + 1 != s[nd << 1]) return query(nd << 1, st, mid);
		else return query(nd << 1 | 1, mid + 1, en);
	}
};

const ll MAX = 1e18 + 5;

SegmentTree seg;
int main() {
	fio();
	int n; cin >> n;
	vector<tpl> q;
	vector<ll> v;
	for (int i = 0; i < n; i++) {
		ll t1, t2, t3; cin >> t1 >> t2 >> t3;
		q.emplace_back(t1, t2, t3);
		v.push_back(t2); v.push_back(t2 - 1); v.push_back(t2 + 1);
		v.push_back(t3); v.push_back(t3 - 1); v.push_back(t3 + 1);
	}
	v.push_back(1); v.push_back(MAX);
	sort(all(v)); v.erase(unique(all(v)), v.end());
	if (v.front() <= 0) v.erase(v.begin());

	int sz = v.size() + 1;
	for (int i = 0; i < n; i++) {
		ll a, b, c;
		tie(a, b, c) = q[i];
		b = lower_bound(all(v), b) - v.begin();
		c = lower_bound(all(v), c) - v.begin();
		if (a == 1) seg.update(1, 0, sz, b, c, 1);
		else if (a == 2) seg.update(1, 0, sz, b, c, -1);
		else seg.update(1, 0, sz, b, c, 2);
		ll ret = seg.query(1, 0, sz);
		cout << v[ret] << endl;
	}
	return 0;
}