图论选做

先开个坑.

有一张图 $Graph(n, m)$ , 现在给定 $n, m$ , 要求你通过 $2m$ 次询问一个边集的最大生成树森林权值和, 得到整张图的最小生成树森林权值和.

$n\le 200, m\le 500$

最小生成树题基本模拟Kru或Br, 随便想想就知道不会是Br, 所以考虑Kru.

考虑从小往大加边, 那么一条边是否加入就直接判断已经得到的边集再加上这条边的最大生成树森林是不是原来的值加上这条边的边权, 如果是就加上, 否则说明它把另一条边顶下去了. 于是就先 $m$ 次问每一条的边权, 再 $m$ 次加边即可.

很套路.

给定 $n$ 点树, 点有点权边有边权, 用Kru求mst, 但每次是选择所有两端点不在同一个连通块中, 编号最小, 且两个连通块的点权和之和大于边权, 按顺序输出选择的边.

$n, m\le 3\times 10^5$

考虑如果限制是, 两边任意一个连通块的和大于边权的做法, 可以每个连通块开数据结构维护出边, 启发式合并, 并且在外面再开一个堆维护所有满足条件的边, 复杂度2log.

然后用这个规约就行了, 若 $a+b>c$, 则 $\min(a, b)\ge \dfrac{c}{2}$, 等这个满足之后, 把这条边删了, 并求出此时的 $a, b$, 现在还需要两个的大小加起来大于 $c-a-b$, 就成功的把问题减了一半, 递归下去即可.

因为一条边删了才加下一个, 所以实际上这个不会多log, 还是2log.

$n$ 个点, 两点边权位点权异或, 求 MST.

注意到两个元素在 $01$ trie上的 $lca$ 的深度就是异或后最高位位置, 于是01trie相当于一个类似kruskal重构树的东西, 那么就直接自底向上合并即可, dfs, 找一个点两个儿子的子树中最小的异或对, 启发式合并即可. 复杂度最后是 $n\log n\log V$

Snuke 将 $n$ 个标志放在一条线上.

第 $i$ 个标志可以放置在坐标 $x_i$ 或坐标 $y_i$ 上.

Snuke 认为当他们中的两个之间的最小距离 $d$ 更大时, 标志看起来更好. 找出 $d$ 的最大可能值.

$n\le 10^4$

考虑一个暴力是二分之后2-sat. 但直接连边会寄, 但2sat也可以线段树优化建图.

给定序列 $A, B$, 求有多少对 $(l, r)$ 满足 $1\le l\le r\le n$, 且
$$
\sum_{i=l}^rB_i+\min_{i=l}^rA_i\le S
$$

首先这题扫描线加分块毫无思维含量.

有意思的是序列分治做法和对最小值分治做法. 最小值分治重点是贡献只枚举一边在另一边二分, 感觉很棒.