11.7 联测

A

莫队复杂度不对啊。

考虑《HH 的项链》的做法，在遍历到一个点 $u$ 的时候加入，在回溯的时候撤销。

B

先做 Type=1。

称边 $(n-1,i)$ 为第 $i$ 条一类边，设一类边总共 $m$ 条。

我们只关心选择的一类边集合 $S$。

答案为 $\sum_S\prod_{i>0} S_i-S_{i-1}$。考虑计数 dp。

设 $f_i$ 表示现在考虑了前 $i$ 条边，钦定第 $i$ 边必选的答案。

不难写出转移 $f_i=1+\sum_{j<i}f_j(i-j)p$，复杂度 $O(n^2)$。

前缀和优化，$pre_i=\sum_{j<i}f_j,ppre_i=\sum_{j\le i}pre_j,f_i=ppre_i+1$。

矩阵快速幂优化。

$\begin{bmatrix}pre' \\ ppre' \\ 1\end{bmatrix}=\begin{bmatrix}1 & 1 & 0 \\p & p+1 & 0 \\1 & 1 & 1\end{bmatrix}\begin{bmatrix}pre \\ ppre \\ 1\end{bmatrix}$

复杂度 $O(27 \log n)$。

再做 Type=2。

枚举 $S$ 中第一条以及最后一条边 $l,r$，则 $ans=\sum_Sf'_{r-l}(m-(r-l))(n-1-(r-l)p)$。

其中 $f'$ 的定义与 $f$ 相似，但是钦定第一条边必选。

同样使用前缀和优化做到 $O(n)$。

还差 $tp=2,p=1$ 的做法。

设 $g(i)$ 表示 $n=i,p=1$ 是的答案。

打表不难发现 $g$ 的前三项为 $1,1,3$。对于 $i>3$，$g(i)=3g(i-1)-g(i-2)+2$。

同样使用矩阵快速幂加速。

C

暴力是枚举每个 $x$，$ans_x=\min S_i+f(i,x)$，$f(i,x)$ 表示 $[1,i]$ 中最小的 $x$ 个 $a_j$ 之和。

设 $pos_x$ 表示 $ans_x$ 的最小决策点。

打表不难发现，$pos_x$ 单调不降。

证明：

反证法，设 $pos_x=i,pos_{x+1}=j,j<i$。

那么有 $f(j,x+1)+S_j<f(i,x+1)+S_i$。

移项 $f(j,x+1)-f(i,x+1)<S_i-S_j$。

又 $f(i,x+1)-f(i,x) \le f(j,x+1)-f(j,x)$。

移项 $f(j,x)-f(i,x) \le f(j,x+1)-f(i,x+1)$。

所以 $f(j,x)-f(i,x)<S_i-S_j$。

所以 $f(j,x)+S_j<f(i,x)+S_i$。

所以 $pos_x \ne i$，矛盾。

于是使用分治优化决策单调性，用主席树求前 $k$ 小之和。