Day12
新知识：Dsu on tree。
在计算树上路径问题中，亦可使用点分治。
思想就是每次只保留重儿子的信息且回溯给父亲，其它点的信息暴力计算然后最后删除。如果是路径问题，记得加入一个子树过后要统一计算一次答案。
复杂度是线对，证明考虑一个点被暴力加的次数为对数次即可（假设加入删除复杂度均摊 \(O(1)\)）
void Dfs(int x, int y, bool f) {
for(int to : G[x]) {
if(to == y or to == son[x]) continue ;
Dfs(to, x, 0);
}
if(son[x]) Dfs(son[x], x, 1);
for(int to : G[x]) {
if(to == y or to == son[x]) continue ;
for(int i = L[to];i <= R[to]; ++i) add(ifn[i]);
}
add(x);
ans[x] = get();
if(!f) {
for(int i = L[x];i <= R[x]; ++i) del(ifn[i]);
maxn = sum = 0;
}
}
至于习题，注意 >= k 的信息数组也是可以计算的。
Digit Tree：显然你考虑 LCA，然后路径分为上升段和下降段，我们在 dsu 的时候钦定了 LCA，枚举 x，那么用 map 记录之前加入的 y 的信息即可。
Day13
Deblo：拆位树上路径算贡献，简单题。
Ridiculous Netizens：树上依赖背包，考虑点分治计算所有点作为中心的答案，同时保证复杂度线对。至于背包部分，考虑根号分治，当 \(V\ge \sqrt m\) 的时候改成记录 \(m/V\) 即可，保证了状态数是 \(\sqrt m\) 级别。
感染：点分治优化前缀优化建图。容易发现一个点能连出去的点是树上是联通的，但是 dfn 不一定连续，但是如果点分治过后就是在一条路径上了。就是看新图中有多少点 in = 0。
考虑每个点拉出子树内所有点，按照 dis 排序然后连边，不用考虑同一条链上互相连边算重的情况，这并不影响。容易发现每个点练出去的都是一段前缀。直接前缀优化建图。
很好证最终边数在线对级别。
幻想乡战略游戏：点分树优化找重心的过程。选点分树根开始，向所有儿子走，判断移动是否优（唯一性）。这个判断就点分树上跳 fa，容斥掉 fa 在来源点的贡献。
Day14
Empty Rectangles：分治到中线 \(mid\)（行），枚举列 \(l,r\)。发现每个 \(k\) 都有一个行决策点。所以维护指针移动预处理，然后合并上下信息即可，复杂度 \(O(m^2k\log n)\)。
拦截导弹：三维偏序的 dp，用 cdq 套 bit 优化 dp。由于计算方案数，所以倒着再 dp 一次算出 i 作为起点的最大值方案数，和终点合并即可。
Day??? 初三杂题巩固
通配符匹配：显然分成多个分配符的段进行 dp，转移有 3 种，条件都是哈希判断，有一个 ? 的转移要前缀和优化。
稻草人：晚测，按照 y 的顺序加入点，就是线段树维护丹钓战的板子，虽然我不是很熟。。
赛道修建：显然一个子树只能上传 1 个有效路径，并且每次我们需要子树贪心地合并。贪心考虑从小的开始匹配。
Day17
矩阵乘法：整体二分，矩阵就是 01 的。
Sequence 数字序列：首先所有数减去 \(i\) 变成不严格旦增。二分的时候计算 2 个边界点的答案。
接水果：套了个二维偏序，注意第一维要强制小于第二维。对于时间轴我们要预先排序。
网络：判断一个点是否被完全覆盖。
Day18
炸弹：显然 ds 优化建图。缩点之后跑一个反向图的 dp，记录 L,R 即可。
PUS：一眼，限制只会划分成 \(O(k)\) 个段，考虑这 \(k\) 个点连向这些段，建一个虚点连向这些点，然后这个虚点用 ds 建图连向这些段即可，最后还是简单 dp 一下。
Tax：先考虑所有边都是出边，那么我们排序过后依次连边。又考虑入边，直接连向反边，边权为 0。想到这里自然地把边给变成点。建图很有网络流的味道。
Duff in Mafia：https://www.becoder.com.cn/article/15997
Day20
选举：显然所有 B 要先选，所以按照 b 排序，答案就是一段后缀全部选 a，前缀选一些 b，这玩意可以枚举选 b 的个数，然后 dp。
有趣的家庭菜园 2：前后互不影响，所以可以合并前后缀答案，线段树优化 dp。
有趣的家庭菜园 3：\(f(i,j,k,0/1/2)\) 表示前 \(i\) 个合法，当前是什么元素，我们考虑此时第 \(j\) 个 op 元素在当前状态下在什么位置，以及 \(j\) 这个地方考虑一下另外两个 op 的移位带来的影响。（显然相同元素相对顺序不会变）
配对游戏：对每一位算贡献，本质是长为 \(n-i\) 的随机 \(1/-1\) 序列前缀最小值不小于 0 的概率，或者可以直接按照题意 dp 转移。
Phoenix and Computers：1. 连续段 dp，很好写。
2.考虑在序列后面加入一段全部是手动开启的电脑段（一），然后中间间隔一个电脑来自动开启。转移系数就是相对顺序的交。然后还要算一下（一）的方案数。（枚举第一个操作位置，两边操作相对顺序固定，合并代价是组合数。这些组合数相加是一个 2 的幂）
Od deski do deski：
Day21
Tree：首先要选联通的。然后结论：边权和 - 直径。所以这个树背包算一下就可以了。
贪玩蓝月：删除操作很麻烦因为两端插入没办法维护前缀，考虑双栈维护前缀。现在考虑一个栈空了怎么办。一种方法是把另一个栈一半搬过来然后重新预处理。定义势能函数：\(F = |siz1 - siz2|\)，一次插入/删除使势能变 \(1\)，消耗 \(O(p)\)。一次重构消耗 \(O(Fp)\)，让势能清 0，也就是变化 \(F\)。所以这样分析下来消耗 1 势能的代价是 \(O(p)\)。
合并的时候枚举一边 V，另一边用 st 表求区间 dp 最大值。
Polarization：最小值考虑每一层边方向一样，下一层方向取反。这样就是 \(n-1\)。考虑最大值，结论是选择重心，子树一些点全部向上，其余向下。
标签：前缀,int,枚举,Day,建图,Inf,考虑,dp From： https://www.cnblogs.com/LCat90/p/18400611