Problem
给定长度为 \(n(1\le n\le 10^5)\) 的序列（\(1\le a_i\le n\)），共有 \(q(1\le q\le 10^5)\) 个询问，支持两种操作：
1 l r 将区间 \([l,r]\) 依次向右移动一位，其中 \(a_r\) 移动到 \(a_l\)。
2 l r k 询问区间 \([l,r]\) 中 \(k\) 出现次数。
本题强制在线:
\[l=((l'+lastans-1)\mod n)+1
\]
\[r=((r'+lastans-1)\mod n)+1
\]
\[k=((k'+lastans-1)\mod n)+1
\]
其中 \(lastans\) 为上一次的答案，初始值为 \(0\)。
当 \(l>r\) 时，交换 \(l,r\)。
Input
一行一个整数 \(n(1 \leq n \leq 10^5)\) .
一行 \(n\) 个整数，表示数组 \(a(1 \leq a_i \leq n)\)
一行一个整数 \(q(1 \leq q \leq 10^5\)
\(q\) 行操作，如题意所述，强制在线，输入的是 \(l',r',k'\)
Output
对于每一个询问输出答案
Sample
Input 1
7
6 6 2 7 4 2 5
7
1 3 6
2 2 4 2
2 2 4 7
2 2 2 5
1 2 6
1 1 4
2 1 7 3
Output 1
2
1
0
0
Input 2
8
8 4 2 2 7 7 8 8
8
1 8 8
2 8 1 7
1 8 1
1 7 3
2 8 8 3
1 1 4
1 2 7
1 4 5
Output 2
2
0
Solution
考虑将序列分块，每一块内的元素用双端队列维护，每一个整块用桶维护块内数字出现次数。每次查询时直接两端零散点暴力计算，整块查询桶值查询即可
修改分两种情况。一种是整块之间的下标移动，发现本质上是当前块的队尾元素移动到了下一个块中。两个块之间只有一个元素发生转移，弹出插入即可实现。另一种是零散点的下标移动，由于点数较少，可将零散点全部取出，在线更改顺序后再重新插入队列即可。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
using namespace std;
const int kmax = 1e5 + 3;
const int kmaxM = 333;
int n, m, a[kmax];
int s[kmax], e[kmax], bl[kmax];
int blo;
int c[kmaxM][kmax];
int p[kmax], res;
deque<int> q[kmaxM];
void Modify(int l, int r) {
if (bl[l] == bl[r]) { // 零散点
int ct = 0, _b = bl[l];
for (; !q[bl[l]].empty(); q[bl[l]].pop_front()) {
p[++ct] = q[bl[l]].front();
}
l -= s[bl[l]] - 1, r -= s[bl[r]] - 1;
int num = p[r];
for (int i = r - 1; i >= l; i--) { // 偏移
p[i + 1] = p[i];
}
p[l] = num;
for (int i = 1; i <= ct; i++) {
q[_b].push_back(p[i]); // 插回
}
return;
}
for (int i = bl[l]; i < bl[r]; i++) { // 整块
int x = q[i].back();
c[i][x]--, c[i + 1][x]++; // 只有一个元素移动
q[i].pop_back(), q[i + 1].push_front(x);
}
int x = q[bl[r]][r - e[bl[r] - 1]];
int tot = 0; // 右端
c[bl[l]][x]++, c[bl[r]][x]--;
for (; !q[bl[r]].empty(); q[bl[r]].pop_front()) {
p[++tot] = q[bl[r]].front();
}
for (int i = 1; i <= tot; i++) {
if (i == r - e[bl[r] - 1] + 1) continue;
q[bl[r]].push_back(p[i]);
}
tot = 0;
for (; !q[bl[l]].empty(); q[bl[l]].pop_front()) { // 左端
p[++tot] = q[bl[l]].front();
}
for (int i = 1; i < l - e[bl[l] - 1]; i++) {
q[bl[l]].push_back(p[i]);
}
q[bl[l]].push_back(x);
for (int i = l - e[bl[l] - 1]; i <= tot; i++) {
q[bl[l]].push_back(p[i]);
}
}
int Calc(int l, int r, int k) {
int ct = 0, _b = bl[l];
for (; !q[bl[l]].empty(); q[bl[l]].pop_front()) { // 先弹出
p[++ct] = q[bl[l]].front();
}
l -= s[bl[l]] - 1, r -= s[bl[r]] - 1; // 区间映射
int res = 0;
for (int i = l; i <= r; i++) {
res += p[i] == k; // 计算
}
for (int i = 1; i <= ct; i++) {
q[_b].push_back(p[i]); // 再插回
}
return res;
}
int Query(int l, int r, int k) {
if (bl[l] == bl[r]) return Calc(l, r, k); // 零散点
int tot = Calc(l, e[bl[l]], k) + Calc(s[bl[r]], r, k); // 单独处理零散点
for (int i = bl[l] + 1; i < bl[r]; i++) {
tot += c[i][k]; // 统计整块
}
return tot;
}
int main() {
cin >> n;
blo = sqrt(n); // 块长
for (int i = 1; i <= n; i++) {
cin >> a[i];
bl[i] = (i - 1) / blo + 1; // 每一个元素对应块的编号
}
for (int i = 1; i <= bl[n]; i++) {
s[i] = (i - 1) * blo + 1;
e[i] = min(i * blo, n); // 设置好块所对应区间
}
for (int i = 1; i <= n; i++) {
q[bl[i]].push_back(a[i]); // 将块中元素弹入队列
c[bl[i]][a[i]]++; // 块中元素统计
}
cin >> m;
for (int i = 1, op, l, r, k; i <= m; i++) {
cin >> op >> l >> r;
l = (l + res - 1) % n + 1; // 强制在线
r = (r + res - 1) % n + 1;
if (l > r) swap(l, r);
if (op == 1) {
Modify(l, r); // 修改
} else {
cin >> k;
k = (k + res - 1) % n + 1;
res = Query(l, r, k); // 查询
cout << res << '\n';
}
}
return 0;
}