AT_abc265_g

考虑不带修改怎么做。

令 $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$ 信息，显然有转移：

然后就可以线段树维护了。

考虑 $\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$。下传同理。