标签：分治 min 线段 记录 mi 即可 贺题 mx
- [SDOI2017] 遗忘的集合 题解 【多项式】
- CF387D George and Interesting Graph 【网络流】网络流题，枚举中心点，贡献拆成 “连向中心点”+“连向其他点”，前半部分统计度数直接算，后边部分二分图匹配即可。
- P4705 玩游戏 【多项式】列出贡献式子，难算的是 \([x^j]A(x)=\sum_{i=1}^na_i^j\)，将其交换求和顺序转成封闭形式相加的形式，卡住我的是 \(\sum_{i=1}^n\frac{1}{1-a_ix} = n - \sum_{i=1}^n\frac{-a_i}{1-a_ix}\)，简单的代数运算但很神秘，后面是 \(\ln{(x)^\prime}\) 的形式，把和式放进 \(\ln\)，变成 \(n\) 个长度为 \(2\) 的多项式相乘，分治求之，最后卷积即可。
- [HNOI2012] 永无乡 【线段树合并】裸题，并查集维护集合，线段树合并维护集合内的排名，查询二分即可。
- P3979 遥远的国度 【树链剖分/线段树】 树剖，链推平，子树最值，换根，换根不好处理，分讨一下发现只有在查询节点在树剖的根和现在的根之间的链上时有影响，直接做即可。
- P1344 追查坏牛奶 【最小割】一个新的思路，求最小边数最小割，把容量变成 \(c\times n+1\)，最小割是 \(flow/n\),边数是 \(flow\ \%\ n\)。
- P2172 [国家集训队] 部落战争 【最大流】简单题，模拟后最小路径覆盖即可。
- P5336 [THUSC2016] 成绩单 【区间DP】看不出来，再次发现自己区间 DP 好菜，首先套路的设状态
f[l][r] 表示区间 \([l,r]\) 取光的代价，写个式子：f[l][r] = min{W(l,r) + a + b * (mx - mi)^2}，发现区间的权值只和 max/min 相关，于是设 g[l][r][mi][mx] 表示区间当前的最优状态，这里不一定取空，增量转移，g[l][r+1][min(mi,val[r+1])][min(mx,val[r+1])] = min(g[l][r][mi][mx])，这里是把 r+1 放进来一起转移，g[l][r][mi][mx] = min(g[l][k][mi][mx] + f[k+1][r])这里相当于是把后半段取掉，注意离散化即可。
- P3454 [POI2007] OSI-Axes of Symmetry 【字符串/计算几何】思路清奇，手玩一下可以发现，如果有对称轴的话，那么按照 “边->角->边” 的形式写下的字符串环一定能分成一个回文链，用叉积代替角度，断环成链哈希判之即可。
- CF1572D Bridge Club【费用流/优化建图】考虑把点按 popcount 奇偶性分类，按题中规则连边，点数 \(n2^n\)，考虑优化，每次增广都会减少 \(n*2-1\) 组匹配，有用的只有 \(k*(n*2-1)\) 组，贪心的选取最大的即可。
- CF1830E Bully Sort【分块/逆序对】分析一下题中的式子实际上是“逆序对数-\(\sum \max(0,|a_i-i|)\)”，考虑交换的影响：减去修改区间中比左端点小的数加上比它大的数，右端点同理，分块+BIT 维护之。
- CF997E Good Subsegments 【扫描线/线段树】区间有序相当于 mx - mi = r - l，即 r = mx - mi - l，经典离线扫描线维护右边的值，答案就是 l-r 所有子区间的答案，只需要维护最小值个数的历史版本和即可。
- CF1004F Sonya and Bitwise OR 【分治/线段树】神题，不带修的话可以直接分治 + 双指针，因为 or 和是单调不降的，并且只有 log 种取值，带修就是借助线段树维护分治过程，将分治“动态化”，维护前缀后缀 or 和即可，pushup 就和朴素分治一样。
标签：分治,
min,
线段,
记录,
mi,
即可,
贺题,
mx
From： https://www.cnblogs.com/Lkkaknoi/p/17716019.html