题解

思路

值域只有三个数。对任意区间，除了记录每个值的出现次数，还可以记录所有九种有序值对 $(x,y)$ 的数量，即左端元素为 $x$、右端元素为 $y$ 的下标对数。答案就是 $(1,0),(2,0),(2,1)$ 三类数量之和。

做法

线段树节点保存三个计数和九个有序对计数。合并左右儿子时，先相加两侧内部的有序对，再加入所有跨越中点的贡献：左侧值 $x$ 的数量乘右侧值 $y$ 的数量。

一次替换由映射 $f(0)=S,f(1)=T,f(2)=U$ 描述。节点中原来属于值 $x$ 的数量全部转移到 $f(x)$；原来属于有序对 $(x,y)$ 的数量全部转移到 $(f(x),f(y))$。映射不要求为排列，因此转移时必须使用全新的数组。懒标记也是一个三元映射；已有映射 $g$ 后再应用 $f$，合成为 $f\circ g$。

若 $N,Q\le200$，可以逐元素模拟并在询问时扫描统计。若没有修改，可预处理每个前缀内九种有序对与三个计数；区间有序对等于右前缀内部数量减去左前缀内部数量，再减去左前缀与目标区间之间的跨越贡献。对于 $N,Q\le5000$，还可以把序列分块，每块维护相同摘要与懒映射，整块操作为常数时间，散块逐元素重建。

证明

节点的计数显然等于区间中各值数量。任意有序下标对要么完全位于左儿子，要么完全位于右儿子，要么左端在左儿子、右端在右儿子；合并式分别且无遗漏地统计这三种情况，因此九类有序对均正确。

替换对每个元素只依赖其原值，所以任意原有序对 $(x,y)$ 替换后恰变为 $(f(x),f(y))$，数量转移正确。懒映射按操作时间复合后与逐次替换完全相同。由归纳法，每次查询得到的节点摘要都与当前真实序列一致，三类下降值对之和即逆序对数。

复杂度

每次操作访问 $O(\log N)$ 个节点，每个节点只处理常数个计数，时间复杂度为 $O((N+Q)\log N)$，空间复杂度为 $O(N)$。