「C.E.L.U-02」苦涩
题目背景
回想起自己的过往的人生,YQH 觉得心中充满了苦涩。如果人生能再来一次,我一定会少做一些傻事,少真香几次,然后大胆地去追寻自己的爱。可惜没有这样一个机会了。
题目描述
在 YQH 的梦中,他看到自己过去的记忆正在不断浮现在自己脑中。这些记忆带给他的是满满的苦涩。他想要强行忘记一些来减轻自己的苦涩。
YQH 的脑中可以被分成 $n$ 个片区,每个片区相当于一个存放记忆的可重集,初始为空。他将进行 $m$ 次这三种操作:
操作 1:区间 $l\sim r$ 的片区中都浮现了一个苦涩值为 $k$ 的记忆。
操作 2:YQH 开始清理 $l\sim r$ 片区的记忆。如果一个片区 $k\in[l,r]$ 且 $k$ 中苦涩值最大的记忆与 $l\sim r$ 片区中苦涩值最大的记忆相等,则将这个苦涩值最大的记忆忘记。如果在同一个片区有多个相同的苦涩值最大的记忆,则只忘记一个。如果这些片区内没有记忆,则无视。
操作 3:YQH 想知道,$l\sim r$ 片区中苦涩值最大的记忆的苦涩值是多少,如果不存在,输出`-1`。
输入输出格式
输入格式
第一行两个数,$n,m$。
接下来 $m$ 行,第一个数代表操作种类 $op$,对于操作 1,有三个数 $l,r,k$,对于操作 2 或 3,有两个数 $l,r$。
输出格式
对于每个操作 3 输出一行,代表答案。
输入输出样例
输入样例 #1
5 4
1 1 3 2
1 2 4 3
2 3 3
3 1 3
输出样例 #1
3
输入样例 #2
6 6
1 1 6 2
1 3 3 2
1 3 4 3
2 3 4
3 3 3
3 4 4
输出样例 #2
2
2
说明
### 样例解释
**样例解释一**
下面为各操作之后 YQH 的大脑的状态:
第一次操作:$\{2\},\{2\},\{2\},\varnothing,\varnothing$
第二次操作:$\{2\},\{2,3\},\{2,3\},\{3\},\varnothing$
第三次操作:$\{2\},\{2,3\},\{2\},\{3\},\varnothing$
第四次操作询问 区间 $1\sim 3$ 的最大值,所以答案是 $3$。
**样例解释二**
下面为各操作之后 YQH 的大脑的状态:
第一次操作:$\{2\},\{2\},\{2\},\{2\},\{2\},\{2\}$
第二次操作:$\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
第三次操作:$\{2\},\{2\},\{2,2,3\},\{2,3\},\{2\},\{2\}$
第四次操作:$\{2\},\{2\},\{2,2\},\{2\},\{2\},\{2\}$
第五次操作询问 $3$ 的最大值,所以答案是 $2$。
第六次操作询问 $4$ 的最大值,所以答案是 $2$。
### 数据范围
|Subtask|n|m|特殊性质|
|:---:|:---:|:---:|:---:|
|$1(10pts)$|$\leq10^3$|$\le10^3$|$\diagdown$|
|$2(20pts)$|$\leq5\times10^4$|$\leq5\times10^4$|没有操作 2|
|$3(10pts)$|$\leq5\times10^4$|$\leq5\times10^4$|操作 2 中 $l=r$|
|$4(20pts)$|$\leq5\times10^4$|$\leq5\times10^4$|$\diagdown$|
|$5(20pts)$|$\leq2\times10^5$|$\leq2\times10^5$|操作 2 中 $l=r$|
|$6(20pts)$|$\leq2\times10^5$|$\leq2\times10^5$|$\diagdown$|
对于 $100\%$ 的数据,$n,m\le2\times10^5,k\le10^9$