2
arc200e
令 ，。若第 位为 ，没有则为 位，连边 。
容斥数：没有边、一条、菊花、三元环。
CF2084G
归纳证明答案只与两边的最大或最小有关。 显然，若先手操作两边则答案与先手要求相反。
等价于放在数轴上，奇数位置有 个，最小化奇偶位置距离之和。设前 个有 个奇数位置的最小代价 。在 和 的间隔加上两边跨过的贡献，为下凸的二次函数。
差分数组单调，维护全局加一次函数，向右平移，插入 。fhq treap 维护 。
arc199c
把 弄成 ， 弄成 。
一个子树在所有排列中都是区间。区间 dp 设 表示 形成子树， 表示 形成森林。
arc199d
设 和 表示长为 宽为 的矩阵的数量和权值和。考虑最后一行，设 ，有 个 的位置 。挖去 行和这 列进入子问题。枚举 ，第 行的方案数 。
abc406g
下凸。维护斜率拐点斜率的变化量和最左边直线的 。
操作 为将斜率绝对值大于 的部分推平为正负 。操作 为 处斜率加 。
arc196_c
容斥。钦定有 个分解线， 段中后面的不能连向前面的，每段中可能还有更小的段，系数为 。
规定一个段以白点结尾。可以合法的前缀中每个黑点都要被前缀中的白点匹配。把所有白点单独拉出来，设它们在原序列中下标为 ，在这个长为 的新序列上 dp。
设 表示最后一段结尾为 的带系数的方案数。
半在线卷积。可以看作 和 卷积，一整层的长度之和保证为 。
CF1349D
鞅与停时定理。
不妨设 。令 ，。递推即可。。
250713 模拟赛 T3
快排：随机一个元素，数小于/等于的有几个，和 比较，向两边递归。期望 。
对每个左端点维护当前递归内的右端点范围。有 ，双指针。数据结构维护增删元素和固定区间比较。
CF1163F
删边最短路。
把 的最短路扔到序列上。求出每个点 和 分叉的位置 ，和 。
对每条边 ，把 更新为 。
每条新最短路对应唯一 。
P9140
同余最短路。
取基准物品 。对剩下的物品求 的最长路。连边 。
要保证没有正权环，基准物品取性价比 最大的即可。因为 ，所以保证足够。
更新时，一个点不会更新回自己，在 个环上转圈两次即可。
CF1515G
有向图环的基。
求出强连通分量。对于每个边双，求出生成树。回路走 次可以抵消。一定存在可以同时过 的回路。 等价于 ，走 加半圈即可。
求出生成树，非树边 可以形成 的环。求出所有环的 。
裴蜀定理，。