题目链接题意一棵有根树 初始时每个点有一个颜色 并且所有点颜色不同 定义路径长度为路径上不同颜色的个数，定义一个点的权值为这个点到根的路径的长度，支持以下操作：将某一个点到根的路径所有的点替换成一种全新的颜色询问某一个点子树权值的平均值题解2操作实际上也就是求和。。我们观察一下1操作一个很自然的想法是修改是把颜色相同的缩起来一块跳。每次执行的操作就是：跳到当前颜色的根->修改->...
题目链接题目大意$N$ 个数（一开始全是 $0$）和 $M$ 个询问：修改第 $i$ 个位置的值为 $a_i = pair(a_l,a_r)$。询问 $l \text{∼} r$ 中最大值的下标。$0 < \text{pair}$；两个 $\text{pair}$ 比较时先比第一维，再比第二维。$n \leq 10^5,m \leq 5*10^5$题解可以发现这个关系有传递性。于是我们...
题目链接题目大意要求你维护一棵树，支持以下操作询问 $(u,v)$ 两点之间的距离将 $v$ 的祖先变成它的 $k$ 级祖先询问深度为 $d$ 的点中最靠右的点是啥。每层一开始的位置关系在输入中给出 每次 $2$ 操作的时候默认插入到子节点中的最右边。题解学了个叫做维护括号序列的东西。。（不知道是不是叫ETT？）括号序列就是在这个点入栈和出栈的时候都记录一次，比如样例1的括号序列就是 12...