4340. [国家集训队 2026]小丑大师的荣耀

【题目描述】

在小丑牌中达成成就「完美主义者 ++」后，伟大的 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 输入】

8 10
1 6 5
3 2 3 8 8
1 3 3
1 4 5
3 2 6 6 8
1 1 2
2 4
1 2 5
3 1 3 2 7
3 2 3 2 3

【样例 1 输出】

0
2
8
3

【样例 2 输入】

9 17
1 6 6
3 1 1 3 3
1 5 1
1 3 4
2 2
1 9 9
1 2 2
1 7 9
2 4
1 2 3
3 1 7 3 3
1 8 6
1 7 5
3 6 9 9 9
1 4 5
2 3
3 3 5 2 9

【样例 2 输出】

0
2
4
16

【样例说明】

在此键入。

【数据规模与约定】

对于所有测试数据，均有：  

- $1 \le m, q \le 2 \times 10^5$；  

- 对于每次操作，均有 $o \in \{1,2,3\}$，且给定的参数均满足【题目描述】中的限制。

特殊性质 A：所有插入卡牌与移除卡牌的操作均在所有询问之前。  

特殊性质 B：不存在移除卡牌的操作。  

特殊性质 C：所有询问均满足 $s = t$ 且 $u = v$。

【来源】

IOI2026中国国家集训队集中培训 Day2 Task2