20244-zuo-ti-ji-lu

4.7

CF1648D

设 $dp_i$ 为从 $(1,1)$ 到 $(2,i)$ 的最小代价。答案为 $\max dp_i+s3_n-s3_{i-1}$。

$$dp_i=max(\max_{l_x\le i} dp_{l_x-1}+s2_i-s2_{l_x-1}-w_x,\max_{l_x\le j\le i} s1_j+s2_i-s2_{j-1}-w_x)$$

前面线段树维护 dp 值，按转移顺序区间 max，单点查。后面从后往前枚举 $i$，不断加入区间，维护 $\max_{x\le y} a(x)+b(y)$。另一个线段树分别维护 $maxa,maxb,maxv$。

CF1949F

不合法情况要么完全包含要么不交，建立树形结构。按 $k_i$ 大小从小到大排序。实时记录每个爱好 $j$ 对应的最后的人 $f_j$。枚举 $i$ 的每个爱好 $j$，如果最后不合法意味着每个 $f_j$ 的爱好都被 $i$ 完全包含，否则找到一组解。如果最后不合法，所有 $f_j$ 的爱好数之和为 $k_i$。

4.16

CF1951F

对于 $i<j$

abc348g

有决策单调性，主席树上二分。

4.18

CF1542E2

枚举前 $i-1$ 位相同，$p_i=x$ 且 $q_i=y$。逆序对数的差异只与后 $n-i-1$ 的排列有关。$dp_{i,j}$ 表示 $i$ 个数有 $j$ 个逆序对。

$$ans=\sum_{i=0}^{n-1} A_n^i \sum_{x=1}^{{n-i-1}\sum_{y=x+1}} \sum_{j=0}^{n2}\sum_{k=0}^{j+x-y-1} dp_{n-i-1,j}\times dp_{n-i-1,k}$$

记 $f_j=\sum dp_k$。

$$ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n2}dp_{n-i-1,j}\sum_{x=1}^{{n-i-1}\sum_{y=x+1}} f_{j+x-y-1}$$

记 $g_j=\sum f_k$。

$$ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n2}dp_{n-i-1,j}\times(g_{j-2}\times(n-i-1)-\sum_{x=1}^{n-i-1}g_{j+x-n+i-2})$$

记 $h_j=\sum g_k$。

$$ans=\sum_{i=0}^{n-1} A_n^i \sum_{j=0}^{n2}dp_{n-i-1,j}\times(g_{j-2}\times(n-i-1)-h_{j-2}+h_{j-n+i-2})$$

abc349g

最直接的就是并查集倍增将两段区间并起来。

可以用类似马拉车的思路得到一个贪心算法。枚举 $i$，用 $ban_{i,j}$ 记录 $i$ 不能是 $j$，维护 $r$ 表示当前已知 $b_1\dotsb b_r$。如果 $i+a_i\ge r$ 就把 $r$ 更新到 $i+a_i$，否则什么也不做。最后在 hash 判断所有 $a_i$ 是不是都满足条件。

4.19

P3380

线段树套 FHQ，查询排名为 $k$ 时二分再查询 $mid$ 的排名，复杂度 $O(n\log^3 n)$。

权值线段树套 FHQ，FHQ 维护位置，查询排名为 $k$ 时线段树上二分，复杂度 $O(n\log^2 n)$。

P7831

拓扑排序转移。当当前是环是拆开 $c$ 最大的边。

CF1778E

按 dfn 序，前缀线性基或合并前后缀线性基。

arc173e

观察到：只能选偶数个，且当 $n=4k+2,k>0$ 时不能全选。

线性基选偶数个数：插入 $a_i\oplus a_1$。