P12118 [NordicOI 2025] 点对处理 / Dodgeball Diplomacy

Python / Java（很）可能无法通过本题。不建议不使用 C/C++。

**这是一道交互题**。我们利用交互来让你强制在线回答询问。 有 $N$ 个点，编号从 $1$ 到 $N$，你需要解决如下 $Q$ 个询问： - $\texttt{a u v p}$，在 $u$ 和 $v$ 之间添加长度为 $p$ 的无向边。 - $\texttt{r}$，删除当前图中最长的无向边。 - $\texttt{d}$，把当前图中连通块两两配对（如果连通块数量为奇数，那就选择一个连通块和大小为 $0$ 的连通块配对），记为 $(A_i,B_i)$。 设有 $k$ 个连通块，令连通块 $A$ 的点数为 $|A|$，最小化 $\displaystyle \sum_{1\le i\le k}||A_i|-|B_i||$。只需要输出最小化后的这个值。

第一行给定两个整数 $N,Q$。 接下来 $Q$ 行查询，每行格式即题目描述三者之一。

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

【样例解释】 注意以下解释只按顺序解释类型为 $\texttt{d}$ 的查询。 - 对于样例 $1$，第一次查询，连通块为 $(1,2,3)$，答案为 $3$，第二次查询，连通块为 $(1,2)$ 和 $(3)$，答案为 $1$。 - 对于样例 $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 \le 10,Q \le 20$ | | $2$ | $10$ | $N \le 2000,Q\le 4000$ | |$3$ | $6$ | 类型 $\texttt{d}$ 的查询不超过 $10$ 次 | | $4$ | $17$ | 类型 $\texttt{a}$ 的查询，满足 $u+1=v$ | | $5$ | $14$ | 满足随着边的建立，$p$ 递增 | | $6$ | $26$ | 满足随着边的建立，$p$ 递减 | | $7$ | $18$ | 无附加限制 |