省选联考 2021 A卷 图函数

这个东西大概是可以转化成对于一个图，我们要支持加边，加边之后询问点对 \((u,v)\) 的对数，其中要求 \(u<v\) 并且 \(u,v\) 可以仅通过编号 \(\ge u\) 的点双向到达。显然等价于对于所有的 \(u\) 计算它可以通过 \(\ge u\) 的点双向到达的点的个数求和。

这个东西看起来像个 Floyd 对吧，显然我们有了一个 \(O(n^3m)\) 的算法，实在是太棒了。

我们想一下问题出在哪里。这相当于是每次在一个二维平面上取一个矩形，然后做一个 Floyd，这实在是太糟糕了，因为 Floyd 难以处理二维类型的信息。

接下来要么我们另辟蹊径，要么我们找到一种神奇的加边方式。发现不会做。

思考一下我们有什么性质还没有用到。这个图实际上是一步步构造出来的，而我们的算法是每次当成一个新图来做。

所以说我们考虑每次加边造成的贡献。发现不会做。

所以说我们考虑每次删边造成的影响。发现更困难了。

类似于 Trie 树上查 xor max 的时候我们可以记录子树内插入时间的 min/max 以维护时间这一维，我们可以记录任意两点互通所需的边编号的 min，就可以维护动态加边这一维，而 Floyd 本身可以维护点编号这一维，我们就做完了。