目录

题目

以下题解里面要是有不对的地方欢迎提醒/打脸。

[WC2006]水管局长

题面：

题解：

首先根据一些常识,我们可以发现，符合要求的边一定在最小生成树上，因为有删边操作，因此我们需要做的就是动态维护最小生成树。

因为删边不好处理，因此我们可以直接倒着处理，这样删边就变成加边了。

因为要维护边，因此我们考虑将每条边都视作一个带权中转点。即对于x --- > y的边，连x ---> now --- > y,其中now为一个带权点。

同时如果已经构成一棵树，我们要再往里面塞边的话，就必须要删掉一条边，否则会构成环。

因此对于一条连接x ---> y，边权为\(k\)的边，我们查询x -- > y路径上边权的最大值\(maxn\)，那么会有2种情况：

• \(maxn > k\)，那么说明插入这条边是优的，因此我们删去最大值所代表的边，加入当前边
• \(maxn \le k\),那么说明保留最大值比较优，所以我们忽略这条边，不进行修改。

然后就可以了。

[FJOI2015]火星商店问题

题面

题解

观察到，如果没有最近d天的限制，那么我们只需要将所有物品按照所属商店的顺序加入可持久化trie树。

如果我们要查询商店编号在\([ll, rr]\)之间的最大xor值，那么我们只需要查询区间\([l, r]\)内的xor最大值即可。

其中\(l\)表示第一个属于查询范围内的物品编号，\(r\)表示最后一个属于查询范围内的物品编号。

具体如何获取这2个编号？因为物品是按照所属商店顺序加入的，所以我们只需要在加入的物品序列中二分一下就可以了。

那么再考虑最近d天的限制。

相当于是查询商店编号属于\([ll, rr]\),时刻属于\([l, r]\) 内的最大xor值。

我们考虑线段树分治。

对于每个询问区间，我们将它的查询时刻区间分成log段，挂在线段树上。

对于每个物品，因为我们需要将物品按照所属商店的顺序加入，因此对于线段树上的每个区间，我们都需要重建整个可持久化trie树。

不过因为物品是一个单点修改，因此就算我们在每个包括了这个物品的区间都放一个这个物品，每个物品也最多放log个。

因此我们在每个包括了这个物品的区间内放一个这个物品，然后每到一个区间，就取出所有在这个区间内出现过的物品，重建整棵trie树。

然后对于每个挂在这个区间上的询问，二分我们需要查询的物品区间，在可持久化trie树上查询并更新这个询问的答案。

最后再输出即可。

复杂度是\(O(nlog^2n)\)的

[USACO13OPEN]阴和阳Yin and Yang

题面

题解

看上去点分搞搞就可以了？

[51nod]1472 取余最大值

题意

有一个长度为n的数组a，现在要找一个长度至少为2的子段，求出这一子段的和，然后减去最大值，然后对k取余结果为0。

问这样的子段有多少个。

题解

之前做过这题的树上版本，可以直接套上来做。

我们考虑点分治，因为拼接2条路径时需要知道最大值是谁，所以不能直接做完个子树就放桶。

我们考虑容斥，先求出所有的路径，按照max从小到大排序，然后每枚举到一条线段，就减去max然后在桶里面找方案，再加入桶。

但是这样会有重复，因此我们单独求出每棵子树内部互相匹配的方案。然后用总方案减去这部分，就得到了答案。

CF1137C Museums Tour

题面

一个国家有 \(n\) 个城市，通过 \(m\) 条单向道路相连。有趣的是，在这个国家，每周有 \(d\) 天，并且每个城市恰好有一个博物馆。

已知每个博物馆一周的营业情况（开门或关门）和 \(m\) 条单向道路，由于道路的设计，每条道路都需要恰好一个晚上的时间通过。你需要设计一条旅游路线，使得从首都：\(1\) 号城市开始，并且当天是本周的第一天。每天白天，如果当前城市的博物馆开着门，旅行者可以进入博物馆参观展览，否则什么也做不了，这一天的晚上，旅行者要么结束行程，要么通过一条道路前往下一个城市。当然，旅行者可以多次经过一个城市。

要求让旅行者能够参观的不同博物馆数量尽量多（同一个城市的博物馆参观多次仅算一次），请你求出这个最大值。

题解

如果我们对原图缩点会怎样？

每个强联通分量的贡献会随着进入的时间而改变。

考虑到\(d\)不大，可以考虑将每个城市拆成\(d\)个单独的点，\((x, i)\)表示点\(x\)在星期i的状态，再用\((x, i)\) ---> \((x, i + 1)\)，然后再缩点。

那么我们会发现，一旦我们可以到达一个点，并且\((x, i)\)是开启状态，那么我们一定可以获得这个贡献，因为我们走\(k\)到达的，一定是某个城市的第\(k\)个状态。因此我们就可以在新图上直接跑最长路了。