推歌：踴り子

洛谷傳送

看起來很能分塊啊！然后一個分塊吧唧一下拍上去就過了。

好的我們還是來看看平衡樹做法。

我們考慮每次操作是什么。發現其實是把 \(a_r\) 的位置移到了 \(a_l\) 的前面，\(a_i\sim a_{r-1}\) 內的所有元素向右平移了一格。這種平移看起來可以用平衡樹維護，所以我們開一顆平衡樹維護（原）下標序列。

又因為我們每次要查詢一種顏色，所以可以把 \(n\) 種顏色分開考慮。給每一種顏色開一顆平衡樹，維護（現）元素的相對順序。每次操作在下標平衡樹上找到要移動的元素并將其在對應顏色的樹上移動，查詢則直接在對應顏色的平衡樹上查詢區間元素數量即可。

然后再拍一個 FHQ 或者什么別的平衡樹上去就可以了。不過碼量肯定比分塊大。