CF817F MEX Queries 题解

题目描述

解题思路

考虑分块。发现 $l$ 和 $r$ 的范围都很大，但是我们只需要知道第一个没有出现的正整数是在哪个位置，然后就能得到答案，所以我们把 $l$、$r$、$r+1$ 离散化，然后用一个数组映射回去，我们求得位置后就可以通过这个映射数组求出具体的值。

依次考虑以下操作：

1. 添加：如果是零散块，那么先标记下传，然后直接重新复制就可；如果是整块，那么直接更新标记；
2. 删除：同上；
3. 反转：这个稍微麻烦一点，基本原理同上，但是需要注意处理整块的时候，需要按照有无标记分为两类处理；
4. 查询：直接遍历每个块，找到第一个空的位置，然后映射回去得到答案，但是我们需要注意，如果第一块的左边界是 $>1$ 的，那么我们直接输出 $1$ 即可。

时间复杂度：$O(能过)$，空间复杂度 O ( n n ) O(n\sqrt n) O(nn

​)。

AC 代码

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
#include
#include
#include
#include
#include
#define B 550
#define N 300005
template<typename T>
inline void read(T &x){
   
	x=0; bool f=1; char ch=getchar();
	while(ch<'0'||ch>'9') f^=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?x:-x; return;
}
template<typename T>
inline void put(T x){
   
	if(