You are given a set of integer numbers, initially it is empty. You should perform n queries.
There are three different types of queries:
1 l r — Add all missing numbers from the interval [l, r]
2 l r — Remove all present numbers from the interval [l, r]
3 l r — Invert the interval [l, r] — add all missing and remove all present numbers from the interval [l, r]
After each query you should output MEX of the set — the smallest positive (MEX ≥ 1) integer number which is not presented in the set.
The first line contains one integer number n (1 ≤ n ≤ 1e5).
Next n lines contain three integer numbers t, l, r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1e18) — type of the query, left and right bounds.
可以离散化之后当作0/1序列,查询MEX就是查询序列第一个为0的位置(注意这里的MEX定义>=1)
操作1. 置1
操作2. 置0
操作3. 区间翻转0/1
然后每次操作完成之后强制查询
可以将查询离线后进行离散化
注意要多加1(MEX=1), r+1
比如[2,3] [5,6] 离散化变成1,2,3,4,原来的4信息丢失了
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int inf = 1e18;
struct tag { // 区间和, 区间最值, 区间加, 区间重置
int resetV;
bool isreset, isrev;
tag() : isreset(false), isrev(false) {}
void apply(tag t) {
if (t.isreset) {
isreset = true;
resetV = t.resetV;
isrev = false;
}
if (t.isrev) {
if (isreset) {
resetV ^= 1;
} else if (isrev) {
isrev = 0;
} else {
isrev = 1;
}
}
}
};
struct nd {
ll sum, len;
nd() :sum(0), len(1) {}
nd operator+ (const nd& b) const {
nd t;
t.len = len + b.len;
t.sum = sum + b.sum;
return t;
}
void apply(tag t) {
if (t.isreset) {
sum = t.resetV * len;
}
if (t.isrev) {
sum = len - sum;
}
}
};
struct lazy {
int n;
vector<nd> a;
vector<tag> tg;
lazy(int _n, vector<nd>& b) : n(_n) {
a.assign(4 * n, nd());
tg.assign(4 * n, tag());
auto bd = [&](auto&& self, int p, int l, int r) -> void {
if (l == r) {
a[p] = b[l];
return;
}
int m = l + r >> 1;
self(self, p << 1, l, m);
self(self, p << 1 | 1, m + 1, r);
pull(p);
};
bd(bd, 1, 1, n);
}
void pull(int p) {
a[p] = a[p << 1] + a[p << 1 | 1];
}
void apply(int p, tag& t) {
a[p].apply(t);
tg[p].apply(t);
}
void push(int p) {
apply(p << 1, tg[p]);
apply(p << 1 | 1, tg[p]);
tg[p] = tag();
}
void modify(int p, int l, int r, int x, int y, tag& t) {
if (r < x || l > y) {
return;
}
if (l >= x && r <= y) {
apply(p, t);
return;
}
push(p);
int m = l + r >> 1;
modify(p << 1, l, m, x, y, t);
modify(p << 1 | 1, m + 1, r, x, y, t);
pull(p);
}
void modify(int x, int y, tag& t) {
modify(1, 1, n, x, y, t);
}
int qr_pos(int p, int l, int r, int x, int y) {
if (r < x || l > y) return -1;
if (l >= x && r <= y) {
if (a[p].sum == a[p].len) {
return -1;
}
if (l == r) return l;
}
push(p);
int m = (l + r) >> 1;
int res = qr_pos(p << 1, l, m, x, y);
if (res != -1) return res;
return qr_pos(p << 1 | 1, m + 1, r, x, y);
}
int qr_pos() {
return qr_pos(1, 1, n, 1, n);
}
};
struct seq {
int op, l, r;
};
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<seq> a(n+1);
vector<int> c(1);
c.push_back(1);
for (int i = 1; i <= n; i++) {
cin >> a[i].op >> a[i].l >> a[i].r;
c.push_back(a[i].l);
c.push_back(a[i].r);
c.push_back(a[i].r+1);
}
sort(c.begin()+1,c.end());
c.erase(unique(c.begin()+1,c.end()),c.end());
int len = c.size() - 1;
vector<nd> b(len+1);
lazy tree(len,b);
for (int i = 1; i <= n; i++) {
tag t;
int l = lower_bound(c.begin()+1,c.end(),a[i].l) - c.begin();
int r = lower_bound(c.begin()+1,c.end(),a[i].r) - c.begin();
if (a[i].op == 1) {
t.isreset = 1, t.resetV = 1;
} else if (a[i].op == 2) {
t.isreset = 1, t.resetV = 0;
} else {
t.isrev = 1;
}
tree.modify(l,r,t);
int res = tree.qr_pos();
cout << c[res] << '\n';
}
return 0;
}