cmll02's blog

记 $f_i$ 表示 $i$ 上传多少个，那么只要数多少序列满足 $f_i<a_i+r\sum\limits_{fa(v)=i} f_v$。

$\sum f_i^0$ 就是方案数。注意到 $\sum f_i^0$ 看上去和 $\sum f_v^1$ 有关，于是设置状态 $F(i,j)=\sum f_i^j$ 就能转移了。

熔池一下下界，然后处理一下使得每个数下界变 $0$。

这个东西一眼凸，所以先 wqs 二分。

转化为选择一个点的代价为 $c$，考虑 $x_i$ 代表第 $i$ 个点是否选择，$d_j$ 代表第 $j$ 个区间是否包含了一个被选择的点，$e_j=1-d_j$。最大价值就是 $m-\min\{c\sum\limits_{i=1}^nx_i+\sum\limits_{j=1}^me_j\}$。

那么有：

1. $e_j+\sum\limits_{i=L_j}^{R_j}\ge 1$；
2. $x_i,e_j\ge 0$。

对偶之后得到 min 里面那堆东西的最小值等于：选出若干区间，使得每个位置被覆盖次数 $\le c$，能选出的最大区间数。

于是可以枚举 $c$，每次贪心选出 $r$ 最小的合法区间。

懒得想怎么写代码所以实现了一个 $log^2$ 做法。

$\det(A-BC^T)=\det(A)\det(I-C^TA^{-1}B)$。

显然要矩阵树，于是构造两个矩阵 $B,C$ 使得 $BC^T=G$。构造方法是点减边。

做过 loj 那个题最后也没切。

学了杜老师的做法，很牛啊。

把 $f(\lfloor n2^{-k}\rfloor)$ 弄到一个矩阵里，转移只与 $\operatorname{lowbit}(n)$ 相关。$O(\log^4n+t\log^3 n)$。

根据相关规定，本内容不予显示。