AT_abc265_g
Nygglatho
·
·
题解
考虑不带修改怎么做。
令 f_{l,r,x,y} 表示 [l,r] 区间内满足 i<j,a_i=x,a_j=y 的 (i,j) 数量，t_{l,r,x} 表示 [l,r] 区间内满足 a_i=x 的 i 的数量。
假如你知道了 [l,mid] 区间和 (mid,r] 区间的 f 和 t 信息，显然有转移：
-
t_{l,r,x}=t_{l,mid,x}+t_{mid+1,r,x}
-
然后就可以线段树维护了。
考虑 \forall i\in [l,r],a_i\gets v_{a_i} 这个操作会对 f_{l,r,x,y} 和 t_{l,r,x} 造成什么影响。
令 f'_{l,r,x,y} 和 t'_{l,r,x} 表示修改后 f 和 t 的值，有：
这样就可以维护修改了。
考虑区间修改怎么维护 lazytag。
你发现如果一个区间 [l,r] 的数先使 a_i\gets x_{a_i} 再使 a_i\gets y_{a_i} 等价于先使 x_i\gets y_{x_i} 再使 a_i\gets x_{a_i}。
然后有了这个性质你就可以维护 lazytag 了。令 b_i 为每次区间修改时的 lazytag，只需要让 b_i\gets v_{b_i} 即可，v 是原题面中的 S,T,U。下传同理。
Submission