情景再现
A
By Margarita
考虑离线，树剖拆成线段情况，每次经过一个点\(i\)就要将当前平衡树内所有值\(z\)减\(k=p_i\)，则分类讨论：
- \(0\le z<k\)：所有值不变
- \(k\le z<2k\)：需要减去\(k\)，由于减少了至少一半，故可以直接暴力修改，总修改次数不超过\(\log z\)次
- \(2k\le z\)：减去\(k\)之后大小关系不变，所以直接打标记区间减
需要注意的是到线段末尾需要删除时，我们应当记录下当前点在平衡树中的位置，从而使得时间复杂度不会退化，\(n\)和\(q\)同阶，总时间复杂度\(O(n\log n\log z)\)。
如果你用fhqtreap写，你就会获得带调试三伯行9kb的代码。
E
学习了一个平面图的性质。
首先考虑顺时针dfs的出栈序列和逆时针dfs的出栈序列，设每个点x在两个出栈序列中对应的位置是a[x]和b[x]，可以证明x能走到y当且仅当a[x]>a[y]&&b[x]>b[y]。那么问题转换成有n个点对(a[],b[])，从中取不存在二位偏序的集合使Σw[]最大且字典序最小。如果不用字典序直接用bit优化最长不上升子序列。要字典序的话，dp的时候维护一个01序列表示选了哪些点。用主席树维护01序列即可。
F
学习了如何线性地进行补图bfs。
考虑暴力跑匈牙利。那么复杂度卡死在边太多。考虑找增广的过程：每次找到左边的未匹配点x和右边的未匹配点y，如果从x可以沿着本来的\(n^2-m\)条边以及新增的返回边可达y，那么这就是一条可行增广路。现在要找满足条件的x,y让a[x]+b[y]最大。
考虑把左边的点x按照a[]大小排序，从大到小bfs，求出每个右边的点被哪个左边点第一个bfs到，然后遍历一遍y能找到最好的(x,y)。
需要补图bfs。不同于普通bfs每走一步的时候枚举与x相连的边寻找vis[y]==0的点，补图bfs时我们直接维护vis[]==0的点的集合，每次枚举集合内元素并查看是否与x相连。考虑复杂度，枚举vis==0集合中的某元素y的时候，如果有一次发现x到y有边，那么y会从集合中删除。如果x到y没有边，我们称y寻边失败一次。所有集合中的点寻边失败总次数是O(m)的。所以加上总共要n次增广，复杂度是O(n(n+m))的。
L
显然有\(O(n2^k)\)的朴素dp，当\(k\)大的时候考虑把第\(i\)个元素映射到\((i\mod k,\lfloor i/k\rfloor)\)上，形成一个\(k\times\lfloor(n-k)/k\rfloor+1\)的矩形，之后原限制就变成了矩形中不能有相邻的\(1\)以及首尾行不能隔位都为\(1\)，那么可以用一个\(O(n2^{2n/k})\)的轮廓线dp解决这个问题。
仔细分析复杂度发现，合法的状态数是链的独立集个数，即为斐波那契数列，约为\(1.618^k\)，故我们有了一个\(O(\min\{n1.618^k,n1.618^{2n/k}\})=O(n1.618^{\sqrt{2n}})\)的做法，可以通过此题。
评价为屑题。