题目描述

题目译自 NordicOI 2025 T1 「Dodgeball Diplomacy」

一个地区有 $N$ 座城市，编号从 $1$ 到 $N$。这些城市之间可以签订条约，表示它们愿意相互合作。

一个联盟是指一组城市，其中每座城市通过一个或多个条约与该组内的其他城市相连。联盟的规模就是该联盟中城市的数量。

每个条约都有一个长度，表示起草该条约所用的页面数。为了减少繁文缛节，城市会不时取消仍在生效的最长条约（即页面数最多的条约）。

除了行政事务，城市之间还会通过联盟间的躲避球比赛进行交流。躲避球比赛遵循以下规则：

• 每个联盟组成一支队伍。
• 联盟两两配对进行比赛。
• 如果联盟数量为奇数，则有一个队伍将与一个规模为 $0$ 的「空联盟」对战。
• 两支规模分别为 $A$ 和 $B$ 的联盟之间的比赛不公平分数为：$|A-B|$。
• 一轮比赛的总不公平分数是所有比赛不公平分数的总和。

你的任务是通过优化联盟的配对方式，计算出可能的最小总不公平分数。

你需要支持 $Q$ 次以下类型的查询：

• $\texttt{a}$：在城市 $u$ 和 $v$ 之间添加一个页面数为 $p$ 的条约。
• $\texttt{r}$：移除当前最长的条约（即页面数最多的条约）。所有页面数均唯一。
• $\texttt{d}$：根据当前的联盟情况，计算躲避球比赛的最小不公平分数。

对于类型为 $\texttt{d}$ 的查询，你必须在处理任何后续查询之前立即给出答案。

输入格式

你需要编写一个程序，按照以下行为运行。每个测试数据会运行一次程序，程序应从标准输入读取以下格式的数据：

• 第 $1$ 行：$N\ Q$
• 接下来的 $Q$ 行，每行符合以下格式之一：
  • $\texttt{a}\ u\ v\ p$
  • $\texttt{r}$
  • $\texttt{d}$

分别对应不同的查询操作。

输出格式

对于每条类型为 $\texttt{d}$ 的查询，程序必须在处理后续查询之前立即输出答案。此外，你需要在每次输出答案后立即刷新输出缓冲区。可以通过以下方式实现：

• C++：std::cout << std::endl;
• Python：print("", flush=True)

上述两种方法都会在输出后自动添加换行符。

3 5
a 1 2 1
a 2 3 2
d
r
d

3
1

在第一次躲避球比赛时，城市 $1,2,3$ 属于同一个联盟。因此，他们将对战一个规模为 $0$ 的空联盟，不公平分数为 $|0-3|=3$。接着，城市 $2$ 和 $3$ 之间的条约被移除。因此，第二次躲避球比赛变成了城市 $1$ 和 $2$ 组成的联盟（规模为 $2$）对战城市 $3$ 组成的联盟（规模为 $1$），不公平分数为 $|2-1|=1$。

6 10
a 2 3 10
a 1 2 5
a 3 4 8
d
r
d
a 4 5 1
a 3 6 7
r
d

4
0
2

在第一次躲避球比赛中，有一个规模为 $4$ 的联盟和两个规模为 $1$ 的联盟，总不公平分数为 $4$。

在第二次躲避球比赛中，有两个规模为 $2$ 的联盟和两个规模为 $1$ 的联盟，总不公平分数为 $0$。

在第三次躲避球比赛中，有三个规模为 $2$ 的联盟，总不公平分数为 $2$。

数据范围与提示

对于所有数据，满足：

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 500000$
• $1 \leq p \leq 10^{9}$
• $1 \leq u \leq N$
• $1 \leq v \leq N$
• 对于类型 $\texttt{a}$ 的查询，$u \neq v$
• 添加条约时，$u$ 和 $v$ 之间不存在已有条约
• 所有页面数 $p$ 均唯一

详细子任务附加限制及分值如下表所示：

子任务编号	分值	附加限制
$1$	$9$	$N \leq 10, Q \leq 20$
$2$	$10$	$N \leq 2000, Q \leq 4000$
$3$	$6$	类型为 $\texttt{d}$ 的查询不超过 $10$ 次
$4$	$17$	对于每条类型为 $\texttt{a}$ 的查询，$u+1=v$
$5$	$14$	条约按页面数递增的顺序创建
$6$	$26$	条约按页面数递减的顺序创建
$7$	$18$	无附加限制