arc 记录 18

痛改前非。

为什么从 18 开始？因为能级也是从 K 开始的！

arc180

arc180c

设 $d{p}_{i,j}$ 为前 $i$ 个前缀和为 $j$。

当前缀和为 $0$ 的时候，规定由最后一个转移，用 $d{p}_{i-1,0}$ 覆盖 $f_{a_i}$。

arc180d

若区间最大值落在中间段，$a_l+a_r+mx$。

若落在左边，中间段长为 $1$。扫描线右端点，弹单调栈的时候线段树上维护 ${\min }_{i=p+1}^{r-1}(a_i+{\max }_{j=i+1}^r{a}_j)$。

181

arc181d

每交换一次逆序对数减 $1$。对于位置 $i$，从第一次 $b_l\ge i$ 操作开始，连续 ${\sum }_{j<i}[a_j>a_i]$ 次操作逆序对数减小。差分。

182

arc182c

维护质数的指数和。$\sum \prod (a_i+b_i)$=$\sum {\sum }_S(a_S{\prod }_{i\notin S}{b}_i)$。矩阵快速幂 $O((2^6{)}^3\log n)$。

arc182d

去掉取模，令 $a_i^{\prime }\equiv a_i(\mathrm{mod}m)$，要求 $|a_i-a_{i-1}|<m$。操作时不改变相对大小关系，答案下界为 $\sum |a_i^{\prime }-b_i^{\prime }$，可以取到。

随便一个合法的 $b_i^{\prime }$。$ans=\min \sum |a_i^{\prime }-b_i^{\prime }-km|$。对 $a_i^{\prime }-b_i^{\prime }$ 排序，尝试中位数附近 $m$ 的倍数。

183

arc183d

权值和最大的上界是 $\sum \min si{z}_u,n-si{z}_u$，当令根为重心且每次删去的两个点属于不同子树时取到。

树的完美匹配形如：子树大小为偶数的 $u$ 和子树大小为奇数的儿子 $v$ 匹配，子树大小为奇数的 $u$ 和父亲匹配。所以删去叶子 $x$ 要求 $x$ 到 $rt$ 的路径上每个点 $u$ 子树大小奇偶性交替，删后反转。

每次取出 $rt$ 的奇偶子树中最大的，各从中删去一个点，优先队列维护。可以保证合法。

根的儿子的子树内删点顺序独立。一个一个子树删，优先删子树大小为奇数的。

184

arc184b

按 $2^i{3}^{j}x$ 分组，组内状压轮廓线。

arc184d

计算操作的方案数，要求只统计不能再进行更多操作的，即两个操作的点之间形成的矩形不能被进一步划分。

185

arc185e

增量算贡献。$an{s}_i=2an{s}_{i-1}+\sum 2^{j-1}gcd(a_i,a_j)$。枚举约数，带 $f_d=d-\sum f_{dd}$ 的系数。