逆天记录 - 3

P9531 [JOISC 2022 Day4] 复兴计划

首先有结论：对于每条边，在最终方案中会被选择的 $X$ 是一个区间。

将所有的边按照边权排序，那么他被选择的代价关于 $X$ 是一个绝对值函数。对于每条边，找出前一条能与他形成环的边，那么分界的 $X$ 就是两条边边权的平均值。

找出每条边的 pre 可以在 $O(nm\alpha(n))$ 的复杂度内完成，并将询问离线，按照 $X$ 排序后维护一堆一次函数的和即可。

CF1801E Gasoline prices

对于每一个形如 $\{(u_1,v_1),(u_2,v_2)\}$ 的限制，等价于将两条路径上对应点并查集合并，最后在同一个并查集中的元素的值必须相等，因此在求出最后并查集的合并情况后，只需要求出每个并查集连通块内部 $L$ 的 $\max$ 与 $R$ 的 $\min$ 即可，这一部分是容易计算的。

接下来考虑如何在合理的复杂度内计算出并查集的合并情况。

首先发现，将所有点全部合并联通只需要进行 $n-1$ 次合并操作，因此有效的合并操作是 $O(n)$ 的，只需要依次找到有效的合并操作即可。

考虑将每个点赋值上他所在并查集的祖先的点权，每次产生一个新的限制时，可以二分两条链上权值组成的序列的 LCP，第一个不同的位置即为需要合并的两个点。

因此只需要支持对于一个树上的单点修改，链上 hash 查询操作，可以直接把树拍成 dfn 序之后用树状数组维护。

时间复杂度 $O(m\log^2n+n\alpha(n)+n\log V)$。

P8162 [JOI 2022 Final] 让我们赢得选举

以下称收获一张票为 A，收获一个支持者为 B。

首先考虑在确定了最终哪几个选择 A，哪几个选择 B 时，一定是先按照 $b_i$ 从小到大依次完成 B，随后以任意顺序完成 A，所需要的时间为 $\sum\frac{b_i}{i}+\frac{\sum a_i}{|B|+1}$。没有很好的贪心选择策略，考虑 dp。

由于 $\frac{\sum a_i}{|B|+1}$ 的存在，因此在不确定 $|B|$ 的前提下，很难对 A 进行 dp，因此首先枚举最终 B 选择了几个。

先按照 $b_i$ 排序，暴力 dp 为 $f_{i,j,k}$ 表示对于前 $i$ 个人，当前 B 选了 $j$ 个，A 选了 $k$ 个，最小的时间是多少，但是这样时间复杂度为 $O(n^4)$，可能可以通过 wqs 二分优化到 $O(n^3\log n)$（我没证过），无法通过。

观察一下性质，在对 $b_i$ 排完序后，如果 $i$ 选择了 B，那么 $< i$ 的位置不可能不选，因为如果位置 $j$ 不选，那么可以选择 $j$ 成为 B 而不选 $i$，这样不会使结果更劣。

因此可以枚举最后一个选 B 的位置是 $i$，那么此时前面已经收获了 $i$ 张票，后面需要的票数是确定的，直接贪心选择前 $k-i$ 小的 $a_j$ 即可。

时间复杂度被优化至 $O(n^3)$，可以通过。

ABC219Ex Candles

首先有很显然的性质，由于吹灭蜡烛不需要时间，因此走到一个蜡烛的位置时一定会吹灭这根蜡烛，因此在对 $a$ 排序后，吹灭的蜡烛一定是一段区间。而没走一步，所有还没有被吹灭的蜡烛的长度都会 $-1$。

但是如果每走一步都将不在区间内的蜡烛长度 $-1$ 的话，会出现一些蜡烛的长度被减至负数的情况，导致计算得到的结果更小。

因此考虑对于 dp 状态加一维，表示仍未熄灭的且最终长度 $\ge 0$ 的蜡烛个数，显然这样不会得到比答案更优的结果。

因此令 $f_{l,r,0/1,i}$ 表示在吹灭的 $[l,r]$ 区间内的蜡烛后，当前在 $0/1$（左/右 端点），还未被吹灭的会记入最终答案的蜡烛个数为 $i$ 的最大答案。转移时，枚举这个蜡烛是否被计入最终答案即可。

时间复杂度 $O(n^3)$。

P3488 [POI2009] LYZ-Ice Skates

不考虑修改，对于一次询问，建立二分图，左边的每个点表示一个人，右边的每个点表示一双鞋，如果存在一个对于左部点的完美匹配，那么答案为 YES。

根据 Hall 定理，对于左部点的任意一个集合，其对应的右部点的集合大小都应该要大于左部点集合大小。

考虑这张二分图的性质，左部的每个点都对应右部的连续 $k(d+1)$ 个点，因此对于左部点，区间的条件不弱于集合的条件，因此只要对于左部点的每个区间合法即可。

考虑左部点 $[l,r]$ 的区间，需要满足 $\sum_{i=l}^r a_i\le k\times (r-l+1+d)$，将每个 $b_i=a_i-k$，只需要满足 $\sum_{i=l}^rb_i\le k\times d$ 即可，因此只需要拿线段树维护 $b$ 的最大子段和即可。

CF1693C Keshi in Search of AmShZ

不难，但是很有借鉴价值的好题。

考虑题目要求求出最坏情况下的最少时间，因此每次走出边时，考虑走到仍未被删除的最坏的出边。

令 $d_u$ 表示从 $u$ 到终点所需要的最少天数。对于一点 $u$，如果没有割掉出边集合 $S$，那么 $d_u=\max_{(u,v)\in S}d_v+deg_u-|S|$。因此最终保留的边的集合一定是按照 $d_v$ 从小到大排序之后的一段前缀。

但是这张图并不是一张 DAG，所以并不能直接求解。考虑在进行 dijkstra 时有性质：当前枚举到的 $dis$ 一定比之前枚举到的 $dis$ 大，因此在进行一次 $v\to u$ 的更新操作时，选择 $d_v$ 作为排序后最后一个选择的没有割边的点，其最短路是 $dis_v+deg_u-cnt_u$，其中 $cnt_u$ 表示已经更新过的 $u$ 的出边数量。

直接跑 dijkstra 即可，时间复杂度 $O(m\log n)$，本题巧妙之处在于利用了 dijkstra 过程中的性质来拟合了题目要求的条件。

P6623 [省选联考 2020 A 卷] 树

考虑每一位分别计算。每个点 $u$ 对他的 $k$ 级祖先会产生 $a_u+k$ 的贡献，考虑将贡献差分，在每一位的 $0/1$ 分界处将差分数组 $\oplus1$，但是这样总的差分数组更改量还是 $O(n)$ 的。

考虑除了第一段，接下来二进制第 $i$ 位的每一个 $0/1$ 连续段的长度都是 $2^i$，因此所有要更改差分的点的深度 $\bmod 2^i$ 都是相等的，因此直接对于每一个二进制位开一个差分数组，$c_{i,s}$ 表示二进制后 $i$ 位为 $s$ 的点的差分应该要异或多少。

直接在 dfs 的时候维护差分数组即可，复杂度 $O(n\log V)$，只需要枚举每个二进制位。

另一种解法是直接维护 01trie，需要支持插入元素，合并 01trie，每个数 $+1$ 与全局求异或和，可以将 01trie 从低位往高位建，这样全局 $+1$ 操作可以通过交换子树来完成，复杂度还是 $O(n\log V)$。

CF1152F2 Neko Rules the Catniverse (Large Version)

由于限制了每个数只能出现一次，如果按照序列的位置 dp，需要记录每个数是否出现，直接爆炸，因此考虑改变 dp 顺序。

考虑从小到大考虑每一个数 $i$，讨论他是否加入序列。

此时如果再记录每个位置是否填了数，那么状态数会飙升至 $2^k$ 往上，再乘上 $n$ 又炸飞了。但是考虑到每个数的具体位置在 dp 过程中并不重要，我们只需要关心每个已经插入的数的相对位置即可，因此可以据此设计 dp 状态。

设 $f_{i,j,k}$ 表示已经考虑插入了 $1\sim i$ 这些数，其中加入序列中的数有 $j$ 个，最后的四种数是否在序列中出现的状态集合为 $k$ 的方案数。

由于题目要求对于相邻两个数，后面的数不能大于前面的数 $+m$，因此对于一个数 $i$，要么放在序列的开头，要么插在前 $m$ 个数之后，要么不放，因此转移如下：

$$\begin{cases} f_{i,j,k}\to f_{i+1,j,k\times 2}\\ f_{i,j,k}\times (\operatorname{popcount}(k)+1)\to f_{i+1,j+1,k\times 2+1} \end{cases}$$

对于 $\{j,k\}$ 一共只有 $k\times 2^m$ 种，因此可以直接矩阵快速幂优化，时间复杂度 $O(k^38^m\log n)$。

P8688 [蓝桥杯 2019 省 A] 组合数问题

组合数转化成了数位 dp，卢卡斯和进制之间的转化，很新奇。

根据卢卡斯定理，有 $\binom{n}{m}\equiv \binom{n/k}{m/k}\times \binom{n\bmod k}{m\bmod k}\pmod k$，发现这个东西就是将 $n,m$ 写成 $k$ 进制后对应位组合数的乘积。

题目要求 $\binom{x}{y}\equiv 0\pmod k$，由于 $k$ 为质数，因此只要 $x,y$ 在 $k$ 进制下任意一位的组合数 $\bmod k=0$ 即可。又由于 $x,y$ 在 $k$ 进制下的每一位都 $< k$，因此其组合数 $=0$ 只有可能是这一位上的 $(a,b)$ 满足 $a < b$。

因此可以对 $n,m$ 为上界，在 $k$ 进制下数位 dp。令 $f_{i,0/1,0/1,0/1}$ 表示考虑了 $k$ 进制的前 $i$ 位，$n$ 是否顶到上界，$m$ 是否顶到上界，是否存在某一位 $(a,b)$ 满足 $a < b$ 的方案数。

转移可以直接分类讨论并计算方案数，时间复杂度 $O(T\log_k n)$。

CF1418F Equal Product

考虑对于满足条件的 $(x_1,y_1,x_2,y_2)$，必有 $x_1\cdot y_1=x_2\cdot y_2$，因此 $\frac{x_1}{x_2}=\frac{y_2}{y_1}=\frac{a}{b}$，因此 $x_2=\frac{x_1}{a}\cdot b,y_2=\frac{y_1}{b}\cdot a$，并且可以证明 $a\mid x_1$ 且 $b\mid y_1$。

通过这个转化，可以发现满足 $a\mid x_1$ 的 $(x_1,a)$ 只有 $O(n\log n)$ 对，可以直接枚举。

对于一个 $x_1$，我们需要找出一对 $(y_1,b)$ 满足如下条件：

$$\begin{cases} \lceil\frac{L}{x_1}\rceil\le y_1\le\lfloor\frac{R}{x_1}\rfloor\\ \frac{x_1}{a}\cdot b\le n\\ y_1\le m\\ a< b \end{cases}$$

发现在 $x_1$ 递增时，$\lceil\frac{L}{x_1}\rceil$ 与 $\lfloor\frac{R}{x_1}\rfloor$ 都是单调不增的，因此可以时刻用一个 set 维护满足第一个条件的 $(y_1,b)$ 数对，每次查询时找到最小的满足 $b>a$ 的数对 $(y_1,b)$，判断其是否满足第二个条件即可。时间复杂度 $O(n\log^2n)$。

CF1774G Segment Covering

考察对于一对相互包含的区间 $[l_i,r_i]\subset [l_j,r_j]$，如果选择了区间 $[l_j,r_j]$，那么多选择一个 $[l_i,r_i]$ 也无妨，因此在选择 $[l_j,r_j]$ 的情况下，奇数方案与偶数方案个数相等，可以直接将 $[l_j,r_j]$ 忽略。

现在问题被转化为了一堆左右端点都递增的线段，求恰好覆盖 $[L,R]$ 的方案数。考虑一次询问怎么做。

设 $f_{i}$ 表示选择了 $[l_i,r_i]$ 线段，且恰好覆盖了 $[L,r_i]$ 这段区间的选偶数个线段的方案 $-$ 选奇数个线段的方案。

初始状态有 $f_1 = -1$，转移为 $f_i=-\sum_{r_j\ge l_i}f_j$。模拟几次转移观察有什么性质。
对于第二条线段 $[l_2,r_2]$，如果 $l_2 > r_1$，那么方案数就变为了 $0$，因为始终无法覆盖中间一段区间，否则 $f_2=1$。
对于第三条线段 $[l_3,r_3]$，如果 $l_1\le l_2\le l_3\le r_1$，那么有 $f_3=f_2+f_1=0$，可以看作 $f_3$ 不存在。

同理地，对于接下来的连续一段满足该条件的线段，都有 $f_i=0$。

直到第一条满足 $l_i>r_1$ 的线段 $i$，如果 $l_i>r_2$，那么 $f_i=0$，后面的 $f$ 也全部为 $0$，否则 $f_i=-f_2=-1$。
这条线段的下一条线段 $i+1$ 也有 $1\to 2$ 类似的转移方式。由此解决了一组询问的问题。

考虑 $p_i$ 表示第一条满足 $l_j> r_i$ 的线段 $j$，那么我们维护这两个 $f$ 值为 $-1$ 与 $1$ 的线段 $x$ 与 $y$，其实是一直在做 $x=p_x,y=p_y$ 操作，如果存在两条线段不交那么就无解。

此时观察到一个很妙的性质，如果中途出现了两条线段不交，那么下一步中后面的线段会走到前面的线段位置上，从而使得这两条线段最终重合。而如果不存在线段不交的情况，那么最后两条线段不会重合。

因此将 $i\to p_i$ 连边，构成一个内向树的结构，每次询问时倍增跳父亲，答案可以根据最后 $x,y$ 的位置计算得出。

CF1305G Kuroni and Antihype

首先考虑加入一个虚点，点权为 $0$，初始时 $0$ 在组织中，这样就能保证最终一定存在一种最优状态是所有人都在组织中的。

假设将一个人加入组织时，被邀请的人也能获得收益，那么一对人相互邀请的贡献是确定了，最后只需要减去所有人的收益和（加入组织实际上是没有收益的）即可。

考虑在能相互邀请的人之间连边，边权为 $a_u+a_v$。原问题等价于求出这棵树的最大生成树。

虽然这棵树的边树可能会很多，但是把相同点权的点缩起来之后，本质不同的边只有 $3^{18}$ 条。可以从大到小枚举边权，然后枚举两边点，用 kruskal 求解最大生成树即可。时间复杂度 $O(n+3^{18}\alpha(3^{18}))$。

CF1019C Sergey's problem

首先考虑忽略第一个限制，找出一个点集使得从这个点集出发走一步能走到所有点。

对于每个点维护一个标记，表示这个点是否能被当前点集中的至少一个点走一步后到达。依次枚举每个点，如果这个点未被标记，那么将这个点加入点集，并将这个点的所有出边能到达的点进行标记。

不难发现这样构造出的点集能在之多一条边内走到所有点，并且这个点集的导出子图是一个 DAG！

证明考虑记录每一个点被标记的时间戳 $t_u$，对于一条边 $u\to v$，如果 $u,v$ 都在点集中，那么一定有 $t_v< t_u$，否则在标记 $u$ 时一定会将 $v$ 标记。因此对于导出子图中的每一条边 $u\to v$，必有 $t_u> t_v$。因此这张导出子图一定是 DAG。

考虑对 DAG 拓扑排序，也类似第一次构造的形式进行标记，那么最终选择的点集内的点至少一步能走到第一次选出的点集，从而保证了至少两步能够到达所有点，也满足的点集内的点两两之间不变的限制。

CF1553I Stairs

不难发现所有极长的连续自然数按顺序组成的区间互不相交，因此可以根据 $a$ 数组推断出连续段依次的长度，假设为 $b$，长度为 $m$。

现在的限制是每个连续段内的值连续且递增或递减，且任意相邻的两个连续段的值域都不能相邻（不然就能拼接起来了，不符合条件）。

考虑容斥，假设钦定 $i$ 对相邻的区间之间的值域是相邻（不合法）的，那么区间被合并为了 $m-i$ 段，给每一段分配数的方案数是 $(m-i)!$，每一个长度 $\ge 2$ 的段能选择递增还是递减。

考虑列出 dp 转移方程，设 $f_{i,j}$ 表示考虑了前 $i$ 段，现在合并出了 $j$ 个连续段的方案数。有：

$$\begin{cases} f_{i,j}=2\times \sum_{k< i} f_{k,j-1} & b_i\not=1\\ f_{i,j}=f_{i-1,j-1}+2\times \sum_{k< i-1} f_{k,j-1} & b_i=1 \end{cases}$$

此时，设 $f_{i,\dots}$ 的生成函数为 $F_i$，$f$ 的前缀和的生成函数为 $G_i$，那么有转移：

$$\begin{cases} \begin{bmatrix}G_{i-1}&F_i\end{bmatrix}=\begin{bmatrix}G_{i-2}&F_{i-1}\end{bmatrix}\times \begin{bmatrix}1&2x\\1&2x\end{bmatrix} & b_i\not=1\\ \begin{bmatrix}G_{i-1}&F_i\end{bmatrix}=\begin{bmatrix}G_{i-2}&F_{i-1}\end{bmatrix}\times \begin{bmatrix}1&2x\\1&x\end{bmatrix} & b_i=1 \end{cases}$$

可以直接通过多项式分治乘法求解出最后的 dp 矩阵，再根据最后的 dp 值容易算出答案。复杂度 $O(n\log^2 n)$。

P8990 [北大集训 2021] 小明的树

有点诈骗的感觉，但是总体还是不错的一道题。以下称点亮的点为白点，未点亮的点为黑点。

题目的合法性要求是所有的白点的子树内都是白点，因此原树中一定存在一些互不相交的全部为白点的子树。而对于所有的黑点，一定都存在于与 $1$ 联通的连通块内。至此，合法条件被转化为了所有的黑点都在一个连通块内。

由于所有黑点的连通块构成的依旧是树的形态，因此对于森林的连通块个数，我们可以通过点数 $-$ 边数计算，也就是在第 $i$ 次操作和，合法的条件等价于 $n-i-$ 连结两个黑色节点的边数 $=1$。

再考虑所有合法状态下对答案的贡献，是所有白点的连通块个数，也就是所有连结黑点与白点的边的个数。

至此，树的形态已经不重要了，我们只关心每个操作后每种边的个数。对于一个询问，我们需要求出所有 $n-i-$ 连结两个黑色节点的边数 $=1$ 的时刻的连结两个黑色节点的边数。

由于 $n-i-$ 连结两个黑色节点的边数 $\ge 1$，所以我们可以直接将两个东西看成一个二元组 $(a,b)$，询问需要求出 $a$ 最小的二元组的 $b$ 之和，可以直接放到线段树上维护，修改时就是区间二元组每个元素的 $+/-$ 操作，容易维护。