CF455D Serega and Fun

推歌：踊り子

洛谷传送

看起来很能分块啊！然后一个分块吧唧一下拍上去就过了。

好的我们还是来看看平衡树做法。

我们考虑每次操作是什么。发现其实是把 \(a_r\) 的位置移到了 \(a_l\) 的前面，\(a_i\sim a_{r-1}\) 内的所有元素向右平移了一格。这种平移看起来可以用平衡树维护，所以我们开一颗平衡树维护（原）下标序列。

又因为我们每次要查询一种颜色，所以可以把 \(n\) 种颜色分开考虑。给每一种颜色开一颗平衡树，维护（现）元素的相对顺序。每次操作在下标平衡树上找到要移动的元素并将其在对应颜色的树上移动，查询则直接在对应颜色的平衡树上查询区间元素数量即可。

然后再拍一个 FHQ 或者什么别的平衡树上去就可以了。不过码量肯定比分块大。