题解 CF817F 【MEX Queries】
RedreamMer
2020-07-28 13:23:56
[$\Large{\texttt{CF817F}}$](https://www.luogu.com.cn/problem/CF817F)
题目调了好久，发片题解纪念下QwQ
算法：线段树+离散化
---
$\Large\texttt{Meaning}$
（题意略有改动）
共有 $n$ 个操作，一个区间（初始全为 $0$ ），共三种操作如下：
$1.$ 将 $[l,r]$ 区间赋值为 $1$ 。
$2.$ 将 $[l,r]$ 区间赋值为 $0$ 。
$3.$ 将 $[l,r]$ 区间的数取反。
每次操作后问最小的正整数 $x$ 且 $a_x$ 为 $0$ 。
$1\le l,r\le 10^{18}$
---
$\Large\texttt{Solution}$
区间修改，查询，首先想到线段树，但是建一个 $10^{18}$ 量级的线段树，时间和空间显然不合理。
但是发现 $n$ 的范围很小，每次修改的区间的左右端点顶多也只有$2*10^{5}$，所以~~套路~~将数据离线下来进行离散化处理，将每个端点排序再依次标号，用数组储存。
然后的操作和普通的线段树没有什么不同，在线段数中对每一段区间存储两个变量( $p_0$ ：区间中是否有 $0$ ， $p_1$ ：区间中是否有 $1$ )。
操作一：$p_0$ 赋值为 $0$ ， $p_1$ 赋值为 $1$ 。
操作二：$p_0$ 赋值为 $0$ ， $p_1$ 赋值为 $1$ 。
操作三：交换 $p_0$ 和 $p_1$ 。
但是需要注意的是（这里我卡了好久）， $\texttt{push\_down}$ 的操作中，对于要下传的标记为3时，若儿子节点的懒标记还没有下传，是不可以直接覆盖的，原因显然。
可是懒标记的特点就是 “懒” ，不可能让操作一直递归下去吧。
所以对此需要进行分类讨论：
若下传的操作是 $1$ 或 $2$ ：可以直接覆盖懒标记，因为这次操作会将整个区间都赋值为 $0$ 或 $1$ ，和之前的操作无关。
若下传的操作是 $3$ ：那么如果懒标记为 $3$ ，可以直接消除懒标记，取反 $+$ 取反 $=$ 不变。
若下传的操作是 $3$ ：如果懒标记为 $1$ ，则就改懒标记为 $2$ ，如果懒标记为 $2$ ，则就改懒标记为 $1$ ，覆盖( $1/0$ )+取反=覆盖( $0/1$ ) （这个操作代码中未体现 ~~其实是我懒的写~~）。
---
$\Large\texttt{Code}$
代码细节还是挺多的，请细细看（码风应该可以令人接受QwQ）
```cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(1)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#include <emmintrin.h>
//qqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzkqqzk
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
// #define PB push_back
// #define MP make_pair
#define ls now << 1
#define rs now << 1 | 1
// #define int long long
// #define us unsigned
#define LL long long
const int N = 1e5;
// const int N = 4e5;
// #define re register
// const int mod = 1e9 + 7;
// const int inf = 0x7fffffff;
// char buf[(int)1e8], *ss = buf;
// inline int INIT()
// {
// buf[fread(buf, 1, (int)1e8 - 1, stdin)] = '\n';
// fclose(stdin);
// return 0;
// }
// const int __START__ = INIT();
inline char nc()
{
static const int BS = 1 << 22;
static unsigned char buf[BS], *st, *ed;
if (st == ed)
ed = buf + fread(st = buf, 1, BS, stdin);
return st == ed ? EOF : *st++;
}
//#define nc getchar
inline LL read()
{
char ch;
LL res = 0;
bool flag = 0;
while (!isdigit(ch = nc()))
;
while (ch >= '0' and ch <= '9')
{
res = (res << 1) + (res << 3) + (ch - '0');
ch = nc();
}
return res;
}
int a, top, id;
LL p[(N << 5) + 10];
map<LL, int> st;
struct node
{
int opt;
LL l, r;
} s[(N << 5) + 10];
struct S
{
int l, r, lazy;
bool p0, p1, qq;
} m[(N << 5) + 10];
inline void up(int now)
{
m[now].p0 = m[ls].p0 | m[rs].p0;
m[now].p1 = m[ls].p1 | m[rs].p1;
}
inline void down(int now)
{
if (!m[now].lazy || m[now].qq)
return;
if (m[now].lazy == 1)
{
m[ls].p0 = m[rs].p0 = 0;
m[ls].p1 = m[rs].p1 = 1;
}
else if (m[now].lazy == 2)
{
m[ls].p0 = m[rs].p0 = 1;
m[ls].p1 = m[rs].p1 = 0;
}
else
{
if (m[ls].lazy)
down(ls);
if (m[rs].lazy)
down(rs);
swap(m[ls].p0, m[ls].p1);
swap(m[rs].p0, m[rs].p1);
}
m[ls].lazy = m[rs].lazy = m[now].lazy;
m[now].lazy = 0;
}
inline void build(int now, int l, int r)
{
m[now].l = l;
m[now].r = r;
if (l == r)
{
m[now].p0 = 1;
m[now].p1 = 0;
m[now].qq = 1;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
up(now);
return;
}
inline void add(int now, int l, int r, int k)
{
if (m[now].l >= l && m[now].r <= r)
{
if (k == 1)
{
m[now].p0 = 0;
m[now].p1 = 1;
}
else if (k == 2)
{
m[now].p0 = 1;
m[now].p1 = 0;
}
else
{
swap(m[now].p0, m[now].p1);
}
if (k == 1 || k == 2)
m[now].lazy = k;
else if (k == 3 && m[now].lazy == 3)
m[now].lazy = 0;
else
{
down(now);
m[now].lazy = k;
}
return;
}
down(now);
int mid = (m[now].l + m[now].r) >> 1;
if (l <= mid)
add(ls, l, r, k);
if (mid < r)
add(rs, l, r, k);
up(now);
}
inline int query(int now, int l, int r)
{
if (m[now].r < l || m[now].l > r || m[now].p0 == 0)
return -1;
if (m[now].p0 == 1 && m[now].p1 == 0)
return m[now].l;
down(now);
int mid = (m[now].l + m[now].r) >> 1;
int k = query(ls, l, r);
if (k != -1)
return k;
return query(rs, l, r);
}
signed main()
{
a = read();
for (int i = 1; i <= a; i++)
{
s[i].opt = read();
s[i].l = read();
s[i].r = read();
if (s[i].l != 1)
p[++top] = s[i].l - 1;
p[++top] = s[i].l;
p[++top] = s[i].l + 1;
if (s[i].r != 1)
p[++top] = s[i].r - 1;
p[++top] = s[i].r;
p[++top] = s[i].r + 1;
}
p[++top] = 1;
sort(p + 1, p + top + 1);
int k = unique(p + 1, p + top + 1) - p - 1;
build(1, 1, k);
for (int i = 1; i <= k; i++)
st[p[i]] = i;
// cout << st[2] << ' ' << st[10];
for (int i = 1; i <= a; i++)
{
add(1, st[s[i].l], st[s[i].r], s[i].opt);
// for (int i = 1; m[i].l; i++)
// cout << i << ' ' << m[i].l << ' ' << m[i].r << ' ' << m[i].p0 << ' ' << m[i].p1 << ' ' << m[i].lazy << endl;
printf("%lld\n", p[query(1, 1, k)]);
}
return 0;
}
```
[$\large\texttt{My Blog}$](https://www.luogu.com.cn/blog/184549/)