城市建设

给你一个加权无向图，有次操作，每次会改变一条边的边权。求每次操作后的 MST 的边权和。

.

离线 CDQ 分治 可撤销并查集

考虑离线算法。容易想到线段树分治 + LCT 的算法（即每次加入一条边或者撤消）。然而这个算法常数过大，并不能过。

首先，如果没有修改操作，那么我们可以很快地使用 kruskal 算法求出 MST 边权和。

如果修改操作很少，假设边集和点集都是级别，修改操作数量是级别。那么我们能否找到一种预处理复杂度关于，询问的复杂度关于的算法？容易发现，在这种情况下，有一些从来没有修改过的边，它会一直在 MST 中。那么我们把这些边预处理出来，然后缩点。这样就能使问题的规模减小。同样的，也会有一些边，他们从来都不在 MST 中，这种边就可以扔了。

更准确地说，对于一个关于（边集）的操作序列，我们将分成：

  • 动态边：受到过修改的边。
  • 静态边：从来没有被修改的边。静态边可以进一步分类：
    • 无用边：从来都不在 MST 中的边。
    • 有用边：有时会出现在 MST 中的边。这其中可以分类：
      • 必须边：一直在 MST 中的边。
      • 非必须边：有时不在 MST 中的边。

为了找出必需边，我们把动态边的权值设成，然后使用 kruskal 算法，这样求出的 MST 中的静态边就是必需边；为了找出无用边，把动态边权值设成，使用 kruskal 算法，不在 MST 中的边就是无用边。

把无用边扔掉，把必需边缩点。这样就减小了问题的规模。

考虑原问题。

首先使用 CDQ 分治，考虑操作区间。对于，我们需要先把的一些动态边变成静态边（如果这些边只在中有修改操作），然后删掉无用边，缩点必需边，递归下去。对于同理。

递归到边界如何计算答案？在递归的过程中使用可撤消（带权）并查集处理所有的压缩操作。边界情况，在并查集中略做修改查询即可。

时间复杂度。

代码

UOJ50 链式反应

题面太长

首先设表示答案，那么对于：

令，设分别为两者的 EGF，可以得到

然后有两种思路。牛迭然后多项式全家桶，常数爆炸。

另一个思路是直接 CDQ 分治。设，那么我们计算即可。

容易发现，上述式子实际上就是贡献到了上。

考虑 CDQ 分治。那么我们的问题就是，统计满足的对的贡献分别是多少。

这里有一个重要的引理：线段树上的区间，一定满足或者。

那么，如果，我们可以直接 FFT 计算对的贡献。

因此，和不可能同时满足。则我们钦定，这样再约束一下的限制条件就可以快速算出对的贡献，把这部分的贡献乘 2 后累加即可。

时间复杂度。

附：CDQ 的重要一步就是计算上下界，把问题规模缩小到与区间长度有关。

代码

IOI2000 邮局

数轴上个整点，从中取个作为关键点，要求最小化每个点到离它的最近关键点的距离的和。

。

摘要：决策单调性，分治优化 DP。

前置知识

对于二元函数，若满足

称满足四边形不等式。

对于一类 1D/1D 的区间 DP

若满足四边形不等式，则也满足决策单调性。

对于形如

的转移方程，其中是代价函数，可以计算。设表示的最优决策，即

如果，即同一层满足决策单调性，那么我们可以考虑分治优化 DP。

具体地，固定，考虑分治地计算。我们首先计算，然后把区间分成两部分，两边递归下去做，求出所有的。由于递归的每一层的规模都是，一共层，因此转移一层的总复杂度（注意，复杂度与是否平衡无关）。

题解

设表示在的点建一个关键点，最小的距离总和。容易发现。可以证明满足四边形不等式。因此使用上述分治算法即可。

代码

UOJ191 Unknown

维护一个向量序列：

  1. 在末尾添加一个向量
  2. 删除末尾的向量
  3. 询问的向量与叉积的最大值

空间较小。。

如果使用二进制分组的话，删除和询问就假了。

考虑一个类似二进制分组的做法，使用线段树维护。插入的时侯，如果两个儿子的区间都满了，就把这个结点的凸壳建出来（凸壳的合并）。否则不建。查询的时候在已经建出凸壳的结点上查。没建出就递归下去。

但是删除还是很假。我加一次删一次重复下去就假了。

考虑延迟合并。在插入的时侯，如果线段树上结点的区间满了，并且的同一层的上一个（左边的）结点还没有建凸壳，就把左边的这个点建了（结点就不管，放在这不动它）。删除的时侯该咋删。这样的复杂度就对了。

总复杂度。