题意理解

我们有 $N$ 个节点（棉花糖），初始给定 $M$ 条边（竹签），要求添加最少的边，使得图满足：

如果 $a < b < c$，并且有边 $(a,b)$ 和 $(a,c)$，那么必须有边 $(b,c)$。

换句话说，对于任意节点 $a$，与 $a$ 相连且编号大于 $a$ 的所有节点之间必须两两相连。

条件转化

这个条件等价于：对于任意 $a$，由 $a$ 和所有与 $a$ 相连且编号大于 $a$ 的节点构成的子图必须是一个完全图。

也就是说，如果 $a$ 与 $b_1, b_2, \dots, b_k$ 相连（且 $b_i > a$），那么 $b_1, b_2, \dots, b_k$ 之间必须两两相连。

问题转化

我们可以这样考虑： 对于每个节点 $i$，设 $S_i = { j > i \mid (i,j) \in E }$（即 $i$ 的邻居中编号大于 $i$ 的集合）。 那么 $S_i$ 必须是一个完全图，否则需要补边。

因此，对于每个 $i$，如果 $|S_i| = k$，那么 $S_i$ 中应该有 $\frac{k(k-1)}{2}$ 条边。 如果 $S_i$ 中实际存在的边数不足，就需要补足。

高效计算方法

直接枚举每个 $i$ 并检查 $S_i$ 中的边数会超时（$O(N^2)$ 不可行）。

我们可以这样优化：

按节点编号从大到小处理（从 $N$ 到 $1$）。

维护每个节点的“右邻居列表”，并按编号排序。

对于节点 $i$，它的 $S_i$ 就是它的右邻居集合。

要检查 $S_i$ 中哪些边已经存在，我们可以利用之前处理过的信息： 对于 $u, v \in S_i$（$u < v$），边 $(u,v)$ 存在当且仅当 $u$ 是 $v$ 的邻居（因为 $u < v$，所以 $u$ 在 $v$ 的右邻居列表中）。

具体算法：

读入边，用邻接表存储（只存编号大的邻居到编号小的邻居？不，我们存双向，但处理时只关心右邻居）。

对每个节点的右邻居列表排序。

从 $N$ 到 $1$ 处理每个节点 $i$：

设 $R$ = $i$ 的右邻居列表。

需要的边数 = $|R| \times (|R|-1)/2$。

实际存在的边数：对 $R$ 中每对 $(x,y)$（$x<y$），检查 $x$ 是否在 $y$ 的右邻居列表中（可以用二分查找，因为列表有序）。

缺失的边数 = 需要的边数 - 实际存在的边数。

累加所有缺失的边数，加上初始的 $M$ 条边，就是答案。

但这样检查每对 $(x,y)$ 还是可能 $O(k^2)$，最坏 $O(N^2)$。

进一步优化

我们可以用更高效的方法计算 $S_i$ 中已经存在的边数：

对于节点 $i$，它的右邻居集合 $R$ 已经排序。 对于每个 $u \in R$，$u$ 的右邻居集合 $R_u$ 与 $R$ 的交集大小，就是 $u$ 在 $S_i$ 中已经连接的邻居数（且编号大于 $u$）。 实现细节 我们可以用 vector adj[N+1] 存储邻接表，并且每个节点的邻居列表排序。

然后对每个 $i$：

$R = adj[i]$ 中大于 $i$ 的部分（其实存储时可以只存大于 $i$ 的邻居，但输入边是双向的，我们存储时只存 $a<b$ 的边？不，我们存储双向，但处理时过滤）。

实际计算时，我们只关心 $i$ 的邻居中编号大于 $i$ 的，所以可以预先对每个节点 $i$ 的邻居排序，然后取后缀。

更简单的方法： 我们只考虑 $a < b$ 的边，然后对每个 $a$，它的右邻居列表自然就是所有 $b$。

这样我们只需要：

读入边 $(a,b)$ 且 $a<b$，加入 $adj[a]$。

对每个 $adj[a]$ 排序。

对每个 $a$，计算需要的完全边数，减去已有的边数。

复杂度分析

排序所有邻居列表：$O(\sum d_i \log d_i)$。

主循环中，对每个节点 $i$，检查所有右邻居的邻居列表交集： 总复杂度 $O(\sum_i \sum_{u \in R_i} (|R_i| + |adj[u]|))$。 最坏情况下是 $O(N^3)$，但实际数据中很难达到，因为度数和是 $O(M)$。

对于 $N, M \le 10^5$，这个算法在随机数据上可以接受，但最坏情况可能超时。