1113

jyh8221 · 2025-11-13 21:38:06 · 个人记录

t1

记录第一次和最后一次出现，维护一个出现次数，在L_i+1，R_i-1,判断对于相同的颜色是否相同即可。

t2

注意到 x 和 \frac{x}{2}，和线段树的2x ，2x+1相似，于是先将序列建成树，转化为树上问题。

考虑现在在点 u，设其值为 a，2u 值为 b，2u+1 值为 c。

注意到 u 的值要变化，要么从 fa 替换，要么从 b,c 替换。

• 当 a<min(b,c) 的时候，因为 a 最小，递归两个儿子处理。

• 当 b<min(a,c) 的时候，交换 a,b，递归两个儿子处理。