超级钢琴
有点类似某道考试题的思路
求第 (K) 大/前 (K) 大区间好像都可以用类似的方法去做
钦定每个点只能和前面的点配对形成区间
用一个堆维护当前的位置 (x) ，左右区间 (l,r)，最优的转移点 (pos) ,最优的权值 (val)
(st) 表维护前缀和的 (mn)
考虑首先对于每个点扫一遍求出这些东西， 用st表查询就可以方便的做了
然后将这些信息都压进堆中
每次取出的一定是当前最优的区间
然后考虑这个区间取出之后要放入哪些新的区间
就是 (l,mid-1) 和 (mid+1,r) 这两个区间的最优转移点和贡献
所以每次都类似的操作就可以了
在堆中取出(K)个元素就是前(K)大了
最小mex生成树
线段树分治，对值域维护一颗线段树
考虑一条权值为 (w) 的边
将其拍在 (0,w-1) 和 (w+1,mx+1) 的区间上
然后遍历线段树，用可撤销并查集维护此时的联通性
如果到了某个叶子节点，此时的 (size=n)， 说明可以不加这个边就将整颗树建好， 输出即可
Yuno loves sqrt technology III
分块黑科技
维护 (vec),(pos)
(vec[i]) 表示(i)这个权值在原序列中出现的所有下标
(pos[i]) 表示(i)这个下标在对应的(vec)中的下标
预处理出每个块之间的答案 (f[i][j]) ，表示 (i) 到 (j) 的答案为 (f[i][j])
然后查询 (l) 到 (r) 时先取出 (l,r) 之间整块的答案作为初始答案
然后考虑两边的散点能否更新答案
对于左边的判断方法就是看 (vec[pos[i]+ans]) 是否小于等于r
右边类似
Treeland and Viruses
显然的思路是建虚树
考虑建出虚树来怎么做
一个 (naive) 的思路是直接暴力BFS
然后考虑如何优化 (BFS) 的过程
直接改成 $dij $就好了