1112总结
周末做题脑袋一团浆糊
T1
参考 11.10 T4 的思路，按照 height 从小到大考虑，这样同时也方便了安排 \(a_i\)，然后发现当前叶子只能有被占用或者继续拓展，如果当前的 height 为 \(i\)，那么拓展到 \(i+1\) 还需要考虑右儿子，所以只记一维是不行的。
于是记 \(dp[x][y]\) 表示当前 height 有 \(x\) 个，height-1 有 \(y\) 个，其实可以不用记高度，因为只需要算答案， \(height\) 增加的时候答案整体增加就可以了。
转移的话还需要套上一层已经安排到的位置，设 \(dp[i][x][y]\) 表示前 \(i\) 个已经被安排，当前 height 有 \(x\) 个，height-1 有 \(y\) 个，由于 height-1 已经被强制选过了，延申过左儿子了，所以不能作为叶子，作为叶子转移的只有 height，这样的话阶段是 \(i\)，然后再是 \(x\)，最后是 \(y\)。保证了无环性。
同阶段转移，顺序先枚举 \(x\)，再枚举 \(y\)，转移到 \(dp[i][x+y][x]\)，容易发现除了 \(0\ 0\) 都是无环的且符合拓扑序的。
不同阶段转移很简单。
小猪猪经常把 height 写成 heigh，我不说是谁。
T2
非常非常妙的一道题。
暴力无非就是并查集，但是如果加边比较多，暴力并查集就寄了。
并查集有交换律，考虑改变并查集运算的顺序，达到加速的目的。
可以用倍增的思路设计一种广义并查集，然后操作就被暂时拆了，\(fa[x][i]\) 表示 \(x\) 为起点的 \(2^i\) 个数的并查集父亲，意义是 \(x,x+1,x+2\cdots\) 的并查集父亲分别为 \(fa[x][i],fa[x][i]+1,fa[x][i]+2\cdots\)。
注意这里的操作是具有整体性的，必须对于 \(2^i\) 个点都满足，才能改广义并查集的父亲。
考虑下放操作，这是简单的，只需要将 \((fa[x][i],i-1)\) 和 \((x,i-1)\) ，\((fa[x][i]+(1<<i-1),i-1)\) 和 \((x+(1<<i-1),i-1)\) 连边就行。
很难从一道题中总结出有用的东西，但是不妨作为一个启发性的思路。
这个思路也可以被认为是
lazy_tag，具体怎么思考会得到不同的启发。
T3
感觉每次考贪心都不会。
考虑先排除掉包含其它线段的线段，变成左右双单调。
然后容易发现选的线段是一段区间，一旦选线段变成选区间，就好做了，朴素的方式是动态规划，可以做到 \(O(n^2)\)，看上去已经不容易优化了。
发现答案的计算方式是比较简单的，考虑最终情况，假设选了 \(i\) 作为终点，那么实际上每个 \(i\) 的贡献是独立的，为 \(-L_i+R_{i+1}\)（注意这里忽略了无交的情况，无交的情况下面再讨论），这里的 \(i\) 不能为 \(n\)，因为 \(n\) 本来就是终点，排序取前 \(k-1\) 大即可。
加上那些被排除的线段，被排除的线段，要么原封不动放回去，不对答案贡献，要么就自成一段，枚举前面选了几个区间就行，取最大值。
注意到，我们对无交的情况，答案计算方式是有问题的，需要和无交情况的最大值再比较一下，无交情况的最大值就是选最长的 \(k-1\) 个。
总的来说，这是一道分类讨论题，先讨论包含的情况变成双单调，再排除无交的情况变为排序贪心。
T4
Boruvka 题。
Boruvka 本质上是把 Prim 和 Kruscal 结合了起来，然后需要求一个 \(mn[i]\) 表示连通块 \(i\) 连出去的所有边的最小值，然后尝试连边。
Boruvka 的过程会进行 \(\log n\) 次，可以这么说，Boruvka 以一个 log 的代价，换来了通过预处理同一连通块求 多个 Prim 中的最小值的机会。
Boruvka 是来自异世界的神秘算法，请和我念：“\(\text{B--oru--vka}\)”
Boruvka 的核心是要求 \(mn[i]\)，但是一般来说也可以用分析连边性质（一般是三元环或者四元环）来减小边数，比如边权为异或的题目，分析 \(Kruscal\) 的过程可以做到 \(n\log^2n\)，而不必拘泥于 Boruvka。
Boruvka
考虑对于连通块怎么求 \(mn[i]\)，一件非常阴间的事情是需要排除掉同一联通块的元素。
如果看成染色，那么就是元素有颜色，就是求全局不同于某个颜色的最小值，区间修改。
还是可以线段树，维护一个最小值和颜色，不同于最小值颜色的次小值，然后就可以做了。
一个矩阵加需要映射成两个。
仿 Kruscal
好困难，不会。
用主席树维护求出整个邻接矩阵，考虑哪些边是有用的。