261016 - 261027
P17694 主旋律
考虑分治，把一个询问拆成 \(\log\) 个分治区间上的询问，然后分讨左右两半 \(\min a\) 的大小关系，设 \(c\) 表示前缀/后缀最小值，不妨先考虑 \(c_l>c_r\)，那么枚举 \(r\)，合法的 \(l\) 形如一段后缀，用双指针维护。对于一个询问 \([L,R]\)，如果是 \(r\) 的指针先碰到 \(R\)，那么直接用前面所有 \(r\) 的答案更新即可。如果 \(l\) 的指针先碰到 \(L\)，那么先用之前的答案更新，剩下的部分只关心 \([L,mid]\) 中 \(b_l\) 的最大值，贡献是 \(\max_{i\in [r,R]}\{c_ib_i-c_imx\}\)，又因为 \(c\) 单调递减，于是可以用线段树维护凸包，需要离线所有询问以做到单层分治 \(O((n+q)\log n)\)，总复杂度 \(O((n+q)\log^2 n)\)。
261016 D
先对每个点分别贪心，肯定是最大的匹配最小的，然后考虑对不同环调整，发现一个点肯定是把若干个区间的环合并起来，于是只要对相邻的环连边，跑最小生成树即可。
qoj20732 Dynamic Adjustment
保序回归可以用 slope trick 刻画：每次插入两个 \(a_i\)，删除一个最大值，贡献是每次删除的值减去 \(\sum a_i\)。这可以用最大费用最大流刻画，考虑维护模拟费用流，增广只有三种情况，分别讨论即可。
uoj981 决战中途岛
变换坐标系后可以把单次移动看成 \((0,0),(0,0),(0,1),(-1,0),(-1,1),(1,0),(0,-1),(1,-1)\) 八种情况，注意到其可以分解成 \((x+y)(1+x^{-1})(1+y^{-1})\)，要求不能走到任意坐标 \(<0\) 的位置。考虑第一项每次选 \(x\) 还是 \(y\)，那么前缀选 \(x^{-1}\) 的次数不能超过选 \(x\) 的次数，\(y\) 同理，于是可以看成是每次向 \((1,\pm 1)\) 走一步的不交叉的三条路径，用 LGV 引理计算即可。
CF2077G RGB Walking
AT_agc072_a [AGC072A] Rhythm Game
CF2147H Maxflow GCD Coloring
AT_agc072_b [AGC072B] AGC Language
AT_arc180_e [ARC180E] LIS and Inversion
AT_agc066_d [AGC066D] A Independent Set
261022 C
261022 D
只需对每种颜色求出其最终占领全部的情况的贡献，设 \(x_i\) 表示当前颜色还剩 \(i\) 个，第一次走到 \(0/n\) 的可能的步数，\(w_i\) 在最终占领全部时取 \(1\)，那么答案就是 \(\sum_i E[x^kw]\)。
直接维护 \(E[x^0w]\sim E[x^kw]\) 那么每个位置有 \(k^2\) 个转移，非常困难。考虑维护 \(f_{r,i}=E[\binom{x}{r}w]\) 对 \(r\in [0,k]\)。转移：\(E[\binom{x}{r}w_i]=p_i(E[\binom{x+1}{r}w_{i-1}]+E[\binom{x+1}{r}w_{i-1}])+(1-2p_i)E[\binom{x+1}{r}w_i]\)。
于是对组合数拆开之后只有 \(f_{r-1},f_r\to f_r\) 的转移，经过手动消元可以得到一轮 \(O(n)\) 的式子，总复杂度 \(O(nk)\)。
最后用拆幂公式 \(x^k=\sum_{i=0}^k\binom{x}{i}S(k,i)i!\) 得到答案。
CF2041N Railway Construction
AT_agc070_b [AGC070B] Odd Namori
qoj8820 Exchanging Kubic 2
CF2174D Secret Message
对于边权最小的 \(n-1\) 条边，不妨设它们形成树。然后需要注意到最多改变两条边就可以变成不是树，证明考虑删 \(2\) 加 \(2\)，不考虑这四条边图有 \(3\) 个连通块，必有两条边连接相同的两个连通块，或者一条边连在一个连通块内部。这样答案不超过 \(sum-w_{n-2}-w_{n-1}+w_n+w_{n+1}\)。然后考虑改一条边的情况，只需要枚举每条边然后求出子树内最大的非树边即可，是二维偏序。
CF2077D Maximum Polygon
对于固定的最大值，只需要维护前缀字典序最大的合法子序列，合法当且仅当把后面全选了之后是可以满足的。之后插入一个点，只需在比末尾大的时候尝试删除末尾即可。设最大值为 \(x\)，那么 \(sum>2x\)，那么如果存在另一个数 \(y\in (x,2x]\)，把 \(y\) 都加进去是更优的，因此这样有用的最大值只有 \(\log V\) 个。复杂度 \(O(n\log V)\)。