1007. 今晚吃老歌

题目描述

许嵩第九张全创作专辑《安泊猜想》于 2026 年 6 月 16 日陆续释出。专辑第四首歌曲名为《老歌》。歌词里写道：

我惊觉老歌里的细节，可惜已然时隔多年； 唱歌的人早已退隐，没等到红遍； 我懂了老歌扣人心弦，因为来自你的长夜……

一首老歌之所以动人，往往不仅仅是因为旋律本身有多么抓耳，更是因为它与你生命中的某段时光产生了共鸣。现在，请你想象一个长度为 $n$ 的音乐时间轴。有些时间段可能被某些歌曲“覆盖”，意味着在这个时间段你与这些歌曲产生了共鸣。这些覆盖可能彼此交错、堆叠。

你需要处理这个时间轴上的三种操作：

• 操作 1：加入一首歌曲，并将对应的时间段覆盖；
• 操作 2：遗忘某一首覆盖对应时间段的歌曲 —— 若有多首歌曲覆盖相同的时间段，只遗忘其中一首；
• 操作 3：给定一段区间，查询假如只保留那些完整落在此区间内的歌曲，那么区间内有多少个时间点恰好被一首歌曲覆盖？

那些“恰好被一首歌曲覆盖”的瞬间，永远留在了我们的长夜里。

形式化地，你需要维护一个可重集合 $\mathcal{S}$，其中每个元素是一个区间 $[L,R]$（$1\le L\le R\le n$）。初始 $\mathcal{S}=\varnothing$。你需要编写程序处理 $q$ 次操作，每次操作给定整数 $op,l,r$。根据 $op$ 的值，你需要处理下列三种操作：

• $op=1$（操作 1）：向 $\mathcal{S}$ 中加入一个区间 $[l,r]$。
• $op=2$（操作 2）：从 $\mathcal{S}$ 中删除一个区间 $[l,r]$。若有多个这样的区间，只删除其中一个。
• $op=3$（操作 3）：计算，若只保留 $\mathcal{S}$ 中满足 $l\le L\le R\le r$ 的区间 $[L,R]$，有多少整数 $l\le k\le r$，使得 $k$ 恰好被一个保留的区间覆盖？

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 3$）表示测试数据组数。

接下来对于每一组测试数据：

第一行包含两个整数 $n,q$（$1\le n,q\le 5\times 10^5$，$\sum n,\sum q\le 1.5\times 10^6$），表示时间轴的长度与操作数。

接下来 $q$ 行，第 $i+1$（$1\le i\le q$）行包含三个整数 $op_i,l_i,r_i$（$1\le op_i\le 3$，$1\le l_i\le r_i\le n$），表示第 $i$ 次操作。

保证对于每一次操作 2，均存在一首覆盖给定时间段的歌曲。

输出格式

对于每一组测试数据，对于每一次操作 3，输出包含一行一个整数表示答案。

样例输入

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

样例输出

0
5
2
5

提示

对于样例测试数据：

• 对于第一次操作 3，没有被该区间完全包含的歌曲，答案为 $0$。
• 对于第二次操作 3，保留歌曲对应的时间段为 $[2,6]$，时间点 $2,3,4,5,6$ 恰好被一首歌曲覆盖，答案为 $5$。
• 对于第三次操作 3，保留歌曲对应的时间段为 $[1,8],[1,8],[1,3],[7,10]$，时间点 $9,10$ 恰好被一首歌曲覆盖，答案为 $2$。
• 对于第四次操作 3，保留歌曲对应的时间段为 $[1,8],[1,3],[7,10]$，时间点 $4,5,6,9,10$ 恰好被一首歌曲覆盖，答案为 $5$。

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1007