CF1375H Set Merging
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
LOJ 分析 容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论：第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
Luogu 分析 考虑对网格图进行分治。 假设当前分治的范围是 $(lx,ly)\sim(rx,ry)$ ，询问的范围是 $ql\sim qr$ 。 找到矩形范围的长边，然后用一条中轴线切成两半。 这时每个询问有两种情况： 查询的两点不在中轴线同侧，此时最短路一定经过了中轴线上的某个点。那么对于中轴线上的每一个点，跑最短路，然后更新询问区间内每个询问的答案。 查询的两点在中轴线同侧，此时最...
Luogu 分析 对修改时间分治，假设当前的时间区间是 $[L,R]$。 考虑以下两种操作： 把 $[L,R]$ 中要修改的所有边修改成 $-\infty$，然后求一遍最小生成树。 发现，如果一条非 $-\infty$ 边在最小生成树中，那它以后一定也在最小生成树中，所以可以把它先加进去。于是可以把所有这样的边形成的连通块缩成一个点。 把 $[L,R]$ 中要修改的所有边修改为$\i...