P14929 [北大集训 2025] 小丑大师的荣耀

在小丑牌中达成成就「完美主义者 ++」后，伟大的 Balatro 贤者 Clonoth 决定考一考你对卡牌游戏的理解。 Clonoth 提出了以下问题：给定一个包含 $n$ 张卡牌的牌堆，每张卡牌的正反面各写有一个 $[1, m]$ 中的正整数。你可以选择若干张卡牌，将其正反面翻转。对于 $1 \le l \le r \le m$，若存在一种翻转方式，使得翻转后 $[l, r]$ 中每个整数 $i$ 都出现在至少一张卡牌的正面，则称区间 $[l, r]$ 是**可覆盖的**。形式化地，设第 $i$ ($1 \le i \le n$) 张卡牌的正反面上的正整数分别为 $a_{i,0}, a_{i,1}$，则 $[l, r]$ 是可覆盖的当且仅当存在一个长度为 $n$ 的 01 串 $s$，满足对于所有 $l \le i \le r$，存在 $1 \le j \le n$ 满足 $a_{j, s_j} = i$。 由于牌堆在游戏中是动态变化的，Clonoth 设计了一个动态场景。具体地，初始时牌堆为空，即 $n = 0$，接下来 Clonoth 将会进行 $q$ 次操作，每次操作是以下三种类型之一： 1. 插入卡牌：给定正整数 $x, y$ ($1 \le x, y \le m$)，令 $n \leftarrow n + 1$，然后向牌堆中插入一张编号为 $n$，正面为 $x$，反面为 $y$ 的卡牌； 2. 移除卡牌：给定正整数 $p$ ($1 \le p \le n$)，满足编号为 $p$ 的卡牌当前仍在牌堆中，然后从牌堆中移除该卡牌； 3. 询问：给定正整数 $s, t, u, v$ ($1 \le s \le t \le m$, $1 \le u \le v \le m$)，你需要求出有多少个区间 $[l, r]$ 满足 $s \le l \le t$, $u \le r \le v$ 且 $[l, r]$ 是可覆盖的。 如果你能正确回答所有询问，Balatro 贤者 Clonoth 就会赠予你一个珍贵的护符——「小丑大师的荣耀」！

从标准输入读入数据。 输入的第一行包含两个正整数 $m, q$，表示卡牌上的数字的范围和操作次数。 输入的第 $i+1$ ($1 \le i \le q$) 行包含若干个正整数，表示第 $i$ 次操作，其中第一个正整数 $o$ 表示第 $i$ 次操作的类型。 - 若 $o = 1$，则该行包含三个正整数 $o, x, y$，表示插入一张正面为 $x$，反面为 $y$ 的卡牌； - 若 $o = 2$，则该行包含两个正整数 $o, p$，表示移除编号为 $p$ 的卡牌； - 若 $o = 3$，则该行包含五个正整数 $o, s, t, u, v$，表示一次询问。

输出到标准输出。 对于每次询问，输出一行一个非负整数，表示满足要求的区间数量。

### 【子任务】 对于所有测试数据，均有： - $1 \le m, q \le 2 \times 10^5$； - 对于每次操作，均有 $o \in \{1,2,3\}$，且给定的参数均满足【题目描述】中的限制。 | 子任务编号 | 分值 | $m, q \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | 1 | 30 | $2000$ | 无 | | 2 | 10 | $2 \times 10^5$ | A | | 3 | 10 | $2 \times 10^5$ | BC | | 4 | 20 | $2 \times 10^5$ | B | | 5 | 20 | $2 \times 10^5$ | C | | 6 | 10 | $2 \times 10^5$ | 无 | 特殊性质 A：所有插入卡牌与移除卡牌的操作均在所有询问之前。 特殊性质 B：不存在移除卡牌的操作。 特殊性质 C：所有询问均满足 $s = t$ 且 $u = v$。