T5_魔术 题解 C∈[1,2]C\IN{[1,2]}C∈[1,2] 暴力模拟即可。时间复杂度：O(NM)O(NM)O(NM) C∈[3,5]C\IN[3,5]C∈[3,5] 没有交换操作，考虑对 aaa 作前缀和达到 O(1)O(1)O(1) 查询即可。 C∈[6,10]C\IN[6,10]C∈[6,10] 留给平衡树的分，应该没人用这个，省略掉。重点讲后面的。 C∈[11,20](AC)C\IN[11,20](\TT{AC})C∈[11,20](AC) 题目需要支持区间交叉交换以及区间查询，考虑线段树。然后考虑如何维护线段树信息和 tagtagtag。 首先考虑在线段树的节点处维护三个序列在对应区间的和。然后对于区间交叉交换操作维护一个置换，这个置换的初值为 {0,1,2}\{0,1,2\}{0,1,2}，表示不交换。 举个例子，当我们要交换 a,ba,ba,b 时，除了对维护的和交换，还需将置换 {1,0,2}\{1,0,2\}{1,0,2}，表示交换前两个值。其他交换如此。这样 tagtagtag 的下传就可以看作根据父节点的置换对子节点的信息进行交换或者复合。就解决了交叉互换问题。 时间复杂度：O(NlogN)O(NlogN)O(NlogN)