前言：又上头了
T1
赛时做法：首先，假设对答案做出贡献的是点x，y，设y的祖先且为x的儿子的点为z，那么显然，把除了z以外的所有都归入集合是最优的，因为这不会影响对y的统计且尽量满足了限制
于是就枚举点x
但这时，我不会了，我知道启发式合并可以做，但我不会（忘了），于是我想线段树合并，事实证明，还是有点难写的，码量上了5k，还另外写了一颗线段树来维护距离一个点最远的点
然后被卡常了
正解：还是考虑上面的转化，但用dfs序转化成序列后用双指针，然后看满足有K种颜色的最小区间，并和当前点的子树或除了当前点的子树的所有点的区间比较然后更新即可
T2
简单题，首先贪心的思路是显然的，每次选最大c[i]个操作
然后考虑快速维护这个过程，考虑减1的性质，就是减后交换一部分区间
于是考虑序列平衡树，每次平衡树查找后划分成4个区间，然后按序合并即可
T3
一道挺有难度且很有意思的题
首先，考虑当前的i和目标j，起点数组为a
假设\(a[i]<a[j]\)，那么每次跳到下落速度更快的一定更优，因为如果在这个位置换，到目标线段的时间一定优于不换，大于就改成下落速度更慢的，类似，于是只考虑第一种
那么最优策略一定是一个类似凸包的轨迹
考虑从上往下扫起点，用单调栈，如果当前的与栈顶没交点就弹
如果当前的和次栈顶的相交时间比栈顶更早，那么就弹
记录当前点的下一个点，设为dw
那么对于每个i，一直跳dw即可，这样是\(n^2\)的
考虑优化，用倍增的思想，把dw看做父亲，就可以倍增跳然后跳到父亲与目标更优的最右的点，然后跳到父亲，最后求交点，没有交点就无解
T4
一道挺有难度且很有意思的题
首先，可以从任意一个点开始，等待一段时间后全部收掉，这是不劣于走两圈的
考虑环，直接段环成链即可，那么对于i，设从s时刻开始走，那么可得不等式：\(s+(j-i)>=T_j\),移项可得\(s>=(T_j-j)-i\),那么s最大就是右边的最大，总时间应再加上n-1即可
那么可得答案式子：\(\min_{i=1}^n(i+\max_{j=i}^{i+n-1}(T_j-j))+n-1\)
首先，内层的j的枚举范围可以改成\(n\times 2\)，因为多出来的j原来的j-n也有，且j比j-n大，所以一定不优
于是就转化成了一个近似固定的形式，由于带修，所以考虑线段树
设\(minn[i]\)表示线段树节点i的左子树的答案，因为我们倍长了数组，\(maxn[i]\)表示线段树节点i的\(T_j-j\)的最大值
建树，修改简单，于是我们考虑如何更新
首先，maxn的更新是简单的，但minn可能由于右子树的改变而改变，于是我们递归左子树并考虑当前的右子树的maxn（设为mmax）对左子树中的节点的影响
分类讨论：1，为叶子，那么就直接考虑不更新和用mmax更新的优劣
2，当前的右子树的maxn更劣，那么右子树中所有答案都无效，则右子树的答案就是\(mid+1+mmax\),但不知道左子树的情况，于是递归左子树
3，当前的右子树更优，那么左子树不会改变，于是递归看右子树的优劣
这样就完成了更新，然后统计答案即可，时间复杂度\(O(n\log^2n)\)
——————————————————————————————————————————————————————————————————————————————
下次加油！！！