CF1446D2 Frequency Problem (Hard Version)
Codeforces 分析 先判掉只有一种数的情况，答案显然为 $0$。 再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。 那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。 这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原...
标签 根号分治 下的文章
- 首页
- 根号分治
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
CF700D Huffman Coding on Segment
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
洛谷5355 [Ynoi2017]由乃的玉米田
Luogu 分析 考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。 那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O...
洛谷4039 [AHOI2014/JSOI2014]拼图
Luogu 分析 看到这个 $n\times m\leq 10^5$，可以考虑根号分治。 $n\leq m$ 首先枚举上下边界 $u,d$。 那么所有拼图可以分为两类：第 $u$ 行到第 $d$ 行均为白色的、第 $u$ 行到第 $v$ 行不均为白色的。 最后的拼法会是所有第一类拼图放在中间，然后左右各接上一个第二类拼图。 于是我们算一下第一类拼图的宽度之和，以及第二类拼图左右最多多少列...
51nod1597 有限背包计数问题
51nod 分析 考虑根号分治。令 $B=\left\lceil\sqrt{n}\right\rceil$，则 $[1,B]$ 内的物品能取完，$[B+1,n]$ 内的物品无法取完。 先考虑 $[1,B]$ 内物品。设 $f_{i,j}$ 表示前 $i$ 种物品和为 $j$ 的方案数，容易写出转移 注意到 $(i,j)$ 的转移点 $(i,k)$ 满足 $k\leq j\land j\eq...
CF1039D You Are Given a Tree
Codeforces 分析 首先询问只有一个的时候很简单，差不多就是 NOIP2018D1T3 ，直接贪心即可。 考虑根号分治： 对于链长 $\leq B$ 的询问，直接暴力求。时间复杂度 $O(nB)$ 。 对于链长 $>B$ 的询问，可以发现答案只有至多 $\frac{n}{B}$ 种，直接二分出相同的段即可。时间复杂度 $O(n\frac{n}{B}\log n)$ 。 可以...