20.CF817F MEX Queries 线段树(Lazy标记练习)

20.CF817F MEX Queries 离散化+区间覆盖+区间反转线段树

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

要求维护集合，初始为空，支持以下操作：

• 1.加入 [ l , r ] [l, r] [l,r]在集合中未出现的数
• 2.删除 [ l , r ] [l ,r] [l,r]在集合中出现的数
• 3.区间反转操作，加入未出现删除出现

每次操作后输出集合MEX

洛谷传送门：CF817F MEX Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：Problem - 817F - Codeforces

题目分析

要求维护集合，初始为空，支持以下操作：

• 1.加入 [ l , r ] [l, r] [l,r]在集合中未出现的数
• 2.删除 [ l , r ] [l ,r] [l,r]在集合中出现的数
• 3.区间反转操作，加入未出现删除出现

每次操作后输出集合 M E X MEX MEX。

分析题目，我们可以发现：如果我们建立权值线段树，叶节点 0 − 1 0-1 0−1分别表示出现和未出现，那么：

• 1 1 1操作等效于区间赋 1 1 1
• 2 2 2操作等效于区间赋 0 0 0
• 3 3 3操作等效于区间反转

考虑对线段树打两个标记，维护区间赋值和区间反转

初始化离散化集合插入点 1 1 1(最小 M E X MEX MEX)，并将所有查询离线到离散化集合中。额外插入所有的 r + 1 r + 1 r+1，然后对离散化集合进行离散化处理。

为啥插入 r + 1 r+1 r+1？ 因为这样可以保证映射关系( l − r l-r l−r内的数一定不会成为答案，而 r + 1 r+1 r+1是可以成为答案的，如果不插入，离散化后的集合就缺失了这个答案的信息)。

属于不完全离散化，离散化的合理性限于答案不会出现在操作区间内的性质。

考虑如何查询：发现这类似查询第 k k k大的思想，直接按照元素个数二分+贪心向左查询即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 6e5 + 10, MOD = 1e9 + 7;

namespace ffastIO {
	const int bufl = 1  1;
        if(mid >= L) flip(lson, L, R);
        if(mid > 1;
        if(tree[ls]