CF455D Serega and Fun

Serega 喜欢寻找乐趣。然而，每个人寻找乐趣的方式都不同。Serega 通过解决查询问题来获得乐趣。一天，Fedor 给他出了这样一个问题。 给定一个由 $ n $ 个正整数组成的数组 $ a $，以及对它的若干查询。查询有两种类型： 1. 对区间 $ [l, r] $（两端都包含）进行一次向右循环平移一位。即将数组中的元素排列为：$ a[l],a[l+1],...,a[r-1],a[r] \rightarrow a[r],a[l],a[l+1],...,a[r-1] $。 2. 统计区间 $ [l, r] $ 中等于 $ k $ 的数的个数。 Fedor 很快地跑来看 Serega 解这道题，而 Serega 也很快就解决了。让我们看看你能否解决它？

第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^{5} $），表示数组的元素个数。第二行包含 $ n $ 个整数 $ a[1],a[2],...,a[n] $（$ 1 \leq a[i] \leq n $）。 第三行包含一个整数 $ q $（$ 1 \leq q \leq 10^{5} $），表示查询的个数。接下来的 $ q $ 行，每行表示一个查询。 由于你需要在线输出查询的答案，题目对查询进行了编码。第一类查询的输入格式为：$ 1\ l'_i\ r'_i $。第二类查询的输入格式为：$ 2\ l'_i\ r'_i\ k'_i $。所有输入中的数字都是整数，满足：$ 1 \leq l'_i, r'_i, k'_i \leq n $。 你需要按如下方式对输入中的查询进行解码： $$ l_i = ((l'_i + lastans - 1)\ \bmod\ n) + 1 \\ r_i = ((r'_i + lastans - 1)\ \bmod\ n) + 1 \\ k_i = ((k'_i + lastans - 1)\ \bmod\ n) + 1 $$ 其中，$ lastans $ 是上一次第二类查询的输出结果（初始时 $ lastans = 0 $）。如果经过变换后 $ l_i > r_i $，你需要交换两者的值。

对于每个第二类（统计）查询，输出一行答案。

由 ChatGPT 5 翻译