维护一个01串，一开始全部都是0
3种操作
1.把一个区间都变为1
2.把一个区间都变为0
3.把一个区间的所有数字翻转过来
每次操作完成之后询问区间最小的0的位置
l,r<=10^18
思路：先离散化（注意一定要把1也离散进去） 然后对每个区间[l,r] 把l-1,r+1也离散进去，最后维护一颗线段树（维护最大值和最小值）
#include <bits/stdc++.h> #define lson i<<1 #define rson i<<1|1 using namespace std; const int maxn = 5e6 + 5; typedef long long ll; struct Tree { int l, r; int mm, mx, lazy; }tree[maxn]; ll Hash[maxn], len; void pushup(int i) { tree[i].mx = max(tree[lson].mx, tree[rson].mx); tree[i].mm = min(tree[lson].mm, tree[rson].mm); } void check(int i) { if (tree[i].mx == 0) { tree[i].mm = tree[i].mx = 1; } else if (tree[i].mm == 1) { tree[i].mm = tree[i].mx = 0; } } void pushdown(int i) { if (tree[i].lazy == 0) return ; if (tree[i].lazy == 1) { tree[lson].mm = tree[lson].mx = 1; tree[rson].mm = tree[rson].mx = 1; tree[lson].lazy = 1; tree[rson].lazy = 1; } else if (tree[i].lazy == 2) { tree[lson].mm = tree[lson].mx = 0; tree[rson].mm = tree[rson].mx = 0; tree[lson].lazy = 2; tree[rson].lazy = 2; } else if (tree[i].lazy == 3) { if (tree[lson].lazy == 3) { check(lson); tree[lson].lazy = 0; } else if (tree[lson].lazy == 1) { check(lson); tree[lson].lazy = 2; } else if (tree[lson].lazy == 2) { check(lson); tree[lson].lazy = 1; } else if (tree[lson].lazy == 0) { check(lson); tree[lson].lazy = 3; } if (tree[rson].lazy == 3) { check(rson); tree[rson].lazy = 0; } else if (tree[rson].lazy == 1) { check(rson); tree[rson].lazy = 2; } else if (tree[rson].lazy == 2) { check(rson); tree[rson].lazy = 1; } else if (tree[rson].lazy == 0) { check(rson); tree[rson].lazy = 3; } } tree[i].lazy = 0; } void build(int i, int l, int r) { tree[i].l = l; tree[i].r = r; if (l >= r) return ; int mid = (l + r) / 2; build(lson, l, mid); build(rson, mid + 1, r); pushup(i); } struct node { ll opt, l, r; }q[maxn]; void updata(int i, int l, int r, int opt) { pushdown(i); int x = tree[i].l, y = tree[i].r; if (tree[i].l == l && tree[i].r == r) { if (opt == 1) { tree[i].mm = tree[i].mx = tree[i].lazy = 1; } else if (opt == 2) { tree[i].mm = tree[i].mx = 0; tree[i].lazy = 2; } else if (opt == 3) { if (tree[i].mx == 0) { tree[i].mm = tree[i].mx = 1; } else if (tree[i].mm == 1) { tree[i].mm = tree[i].mx = 0; } tree[i].lazy = 3; } return ; } int mid = (tree[i].l + tree[i].r) / 2; if (mid >= r) { updata(lson, l, r, opt); } else if (l > mid) { updata(rson, l, r, opt); } else { updata(lson, l, mid, opt); updata(rson, mid + 1, r, opt); } pushup(i); } ll query(int i) { pushdown(i); if (tree[i].l == tree[i].r) { return tree[i].l; } int mid = (tree[i].l + tree[i].r) / 2; if (tree[i * 2].mm == 0) { return query(lson); } else { return query(rson); } } /**/ int main() { int n; scanf("%d", &n); Hash[++len] = 1; for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &q[i].opt, &q[i].l, &q[i].r); Hash[++len] = q[i].l; Hash[++len] = max(q[i].l - 1, 1LL); Hash[++len] = q[i].r; Hash[++len] = q[i].r + 1; } sort (Hash + 1, Hash + len + 1); len = unique(Hash + 1, Hash + len + 1) - Hash - 1; build(1, 1, len); for (int i = 1; i <= n; i++) { q[i].l = lower_bound(Hash + 1, Hash + len + 1, q[i].l) - Hash; q[i].r = lower_bound(Hash + 1, Hash + len + 1, q[i].r) - Hash; updata(1, q[i].l, q[i].r, q[i].opt); printf("%lld\n", Hash[query(1)]); } return 0; }
