嘟嘟嘟
这题一直在我的某谷任务计划里，不知为啥一直没做。
现在看起来很水啊，就是离散化+线段树。可能是当时没想明白怎么离散化吧。
就是先把算有区间端点都离线下来，然后把(l - 1, l, l + 1, r - 1, r, r + 1)离散一下。接着就是普通的线段树了。
同时维护区间最小0和1的出现位置，这样区间反转就交换这两个值就行了。
当然还有两个细节，关于离散化的：
1.别把0搞进去了。
2.要手动添加1，因为有的数据可能没有1，但答案却可能出现。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxm = 1e5 + 5;
const int maxn = 6e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, cnt = 0;
ll a[maxn];
struct Que
{
int op; ll l, r;
}q[maxm];
int l[maxn << 2], r[maxn << 2], cov[maxn << 2], rev[maxn << 2], pos[2][maxn << 2];
In void pushup(int now)
{
if(~pos[0][now << 1]) pos[0][now] = pos[0][now << 1];
else pos[0][now] = pos[0][now << 1 | 1];
if(~pos[1][now << 1]) pos[1][now] = pos[1][now << 1];
else pos[1][now] = pos[1][now << 1 | 1];
}
In void build(int L, int R, int now)
{
l[now] = L, r[now] = R;
cov[now] = -1;
if(L == R) {pos[0][now] = L; pos[1][now] = -1; return;}
int mid = (L + R) >> 1;
build(L, mid, now << 1);
build(mid + 1, R, now << 1 | 1);
pushup(now);
}
In void pushdown(int now)
{
if(~cov[now])
{
cov[now << 1] = cov[now << 1 | 1] = cov[now];
rev[now << 1] = rev[now << 1 | 1] = 0;
pos[cov[now]][now << 1] = l[now << 1]; pos[cov[now] ^ 1][now << 1] = -1;
pos[cov[now]][now << 1 | 1] = l[now << 1 | 1]; pos[cov[now] ^ 1][now << 1 | 1] = -1;
cov[now] = -1;
}
if(rev[now])
{
rev[now << 1] ^= 1; rev[now << 1 | 1] ^= 1;
swap(pos[0][now << 1], pos[1][now << 1]);
swap(pos[0][now << 1 | 1], pos[1][now << 1 | 1]);
rev[now] = 0;
}
}
In void update1(int L, int R, int now, bool flg)
{
if(l[now] == L && r[now] == R)
{
cov[now] = flg; rev[now] = 0;
pos[flg][now] = L; pos[flg ^ 1][now] = -1;
return;
}
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) update1(L, R, now << 1, flg);
else if(L > mid) update1(L, R, now << 1 | 1, flg);
else update1(L, mid, now << 1, flg), update1(mid + 1, R, now << 1 | 1, flg);
pushup(now);
}
In void update2(int L, int R, int now)
{
if(l[now] == L && r[now] == R)
{
rev[now] ^= 1;
swap(pos[0][now], pos[1][now]);
return;
}
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) update2(L, R, now << 1);
else if(L > mid) update2(L, R, now << 1 | 1);
else update2(L, mid, now << 1), update2(mid + 1, R, now << 1 | 1);
pushup(now);
}
int main()
{
m = read();
for(int i = 1; i <= m; ++i)
{
q[i].op = read() - 1, q[i].l = read(), q[i].r = read();
if(q[i].l ^ 1) a[++cnt] = q[i].l - 1;
a[++cnt] = q[i].l; a[++cnt] = q[i].l + 1;
if(q[i].r ^ 1) a[++cnt] = q[i].r - 1;
a[++cnt] = q[i].r; a[++cnt] = q[i].r + 1;
}
a[++cnt] = 1;
sort(a + 1, a + cnt + 1);
n = unique(a + 1, a + cnt + 1) - a - 1;
build(1, n, 1);
for(int i = 1; i <= m; ++i)
{
int L = lower_bound(a + 1, a + n + 1, q[i].l) - a;
int R = lower_bound(a + 1, a + n + 1, q[i].r) - a;
if(q[i].op < 2) update1(L, R, 1, q[i].op ^ 1);
else update2(L, R, 1);
write(a[pos[0][1]]), enter;
}
return 0;
}