2022寒假刷题计划（2）

因为上一篇博客园渲染变卡了

2.4

P3258 [JLOI2014]松鼠的新家

简单地差分一下dfs统计就好了。

P4041 [AHOI2014/JSOI2014]奇怪的计算器

比较有意思的题。如果把所有 \(x\) 排序一起全体操作会发现，这些操作不会改变 \(x\) 之间的相对大小关系，同时也就有，每次操作后可能会超过值域范围限制的是左右的某两个区间。所以我们发现只要对 \(x\) 排序后维护区间操作。
具体地，我们需要维护区间最大值和区间最小值，用于判断值域范围限制和求最终单点答案。
同时我们需要支持的操作有区间加，区间乘，区间加特殊值（操作4），以及区间覆盖（值域限制）。
现在我们维护一个特殊的函数 \(f(k1,k2,k3)\)，也就是区间维护三个 lazy tag，\(x=x\times k1+a[t]\times k2+k3\)（其中的 \(a[t]\) 是以 \(a[l]\) 和 \(a[r]\) 对应 \(minn\) 和 \(maxn\) 的修改。）这个函数支持我们上述四种操作。
区间加就是 \(f(1,0,a)\)，区间乘就是 \(f(a,0,0)\)，区间加特殊值就是 \(f(1,a,0)\)，区间覆盖就是 \(f(0,0,a)\)。
然后下传标记时注意下儿子标记的变化，以及注意把没有打 lazy tag 的 \(k1,k2,k3\) 分别令为 \(1,0,0\) 可以避免一些不必要的麻烦。

2.5

P6628 [省选联考 2020 B 卷] 丁香之路

对我有点启发。
我们发现满足条件的路径其实是一条类似欧拉路的东西，也就是说除了起点和终点的度数是奇数，中间经过的点度数为偶数。
我们考虑先把所有必经的边都处理了，把必经边连接的点度数加上，这些必经边距离是一定在答案里的。（我们可以先处理必经边再枚举终点。）
然后发现连完可能不满足上述度数要求，所以我们考虑贪心地选择相邻的两个奇点连接，这样把所有奇点都变成偶点（对于起点和终点可以先把度数++），然后考虑到路径的连通性，我们把一条 \(x\rightarrow y\) 的路径拆成 \(x\rightarrow x+1\rightarrow x+2\rightarrow\cdots\rightarrow y\)，这样路径长度不会改变，同时中间节点的奇偶性也不变，但连接了更多的点，让路径的连通性更好，具体操作可以从小到大枚举，遇到奇点就连接自己和下一个点。
这样做可以把所有点的度数按要求调整好，并且花费最小。但是即使像上面一样拆边操作完我们的路径仍然可能不连通，所以我们现在要把许多连通块连接，一个显然的想法是求出两两连通块之间的距离求最小生成树，然后为了保证节点度数要求这棵树要来回走，答案就要加上最小生成树大小的两倍。
但是这样的边数是 \(n^2\) 的，并不优。我们联想到上面的拆链做法，其实两个连通块的距离可以拆成他们与中间某个连通块距离之和，所以我们需要处理的边就是相邻不同连通块的距离，边数变成了 \(n\)。这样我们的复杂度就是 \(O(n^2\log n)\) 了。

关于这种做法的正确性，因为这种神秘做法不是很好证明最优，所以我自己随便口胡了一会。
应该是把整个路径求解的过程变成两部分，一是满足路径的度数要求，二是满足路径的连通性。
然后前面修改度数的做法是贪心做的，第一部分是局部最优的，然后再满足路径度数的基础上，满足路径连通性的做法是最小生成树，也是局部最优的，两者都是局部最优，所以整个做法是最优的。