链接：

题意：

给出一个序列，两种操作 

1.a[l], a[l + 1], ..., a[r - 1], a[r] 　　→ 　　a[r], a[l], a[l + 1], ..., a[r - 1].

2.在线询问区间[l,r]中值等于k的数有多少个 

题解：

分块，每一块用双端队列表示就可以了，就是写的时候有很多细节要注意

代码：

31 int n, q; 32 int a[MAXN]; 33 int b[350][MAXN]; 34 deque
     
       Block[350]; 35 int cap, num, L[MAXN], R[MAXN], Belong[MAXN]; 36  37 void init() { 38     cap = sqrt(n); 39     num = n / cap; 40     if (n%cap) num++; 41     rep(i, 1, n + 1) Belong[i] = (i - 1) / cap + 1; 42     rep(i, 1, num + 1) { 43         L[i] = (i - 1)*cap + 1; 44         R[i] = i*cap; 45     } 46     R[num] = n; 47     rep(i, 1, num + 1) { 48         rep(j, L[i], R[i] + 1) { 49             Block[i].pb(a[j]); 50             b[i][a[j]]++; 51         } 52     } 53 } 54  55 void update(int l, int r) { 56     if (Belong[l] == Belong[r]) { 57         int id = Belong[l]; 58         l -= L[id], r -= L[id]; 59         int t = Block[id][r]; 60         per(i, l + 1, r + 1) Block[id][i] = Block[id][i - 1]; 61         Block[id][l] = t; 62         return; 63     } 64     int id1 = Belong[l]; 65     int id2 = Belong[r]; 66     int t1 = Block[id2][r - L[id2]]; 67     int t2 = Block[id1][R[id1] - L[id1]]; 68     b[id1][t2]--; 69     b[id2][t1]--; 70     per(i, l + 1, R[id1] + 1)  71         Block[id1][i - L[id1]] = Block[id1][i - L[id1] - 1]; 72     Block[id1][l - L[id1]] = t1; 73     b[id1][t1]++; 74     rep(i, id1 + 1, id2) { 75         Block[i].push_front(t2); 76         b[i][t2]++; 77         t2 = Block[i].back(); 78         Block[i].pop_back(); 79         b[i][t2]--; 80     } 81     per(i, L[id2] + 1, r + 1) 82         Block[id2][i - L[id2]] = Block[id2][i - L[id2] - 1]; 83     Block[id2][0] = t2; 84     b[id2][t2]++; 85 } 86  87 int query(int l, int r, int k) { 88     int res = 0; 89     if (Belong[l] == Belong[r]) { 90         int id = Belong[l]; 91         rep(i, l, r + 1) if (Block[id][i - L[id]] == k) res++; 92         return res; 93     } 94     int id = Belong[l]; 95     rep(i, l, R[id] + 1) if (Block[id][i - L[id]] == k) res++; 96     rep(i, Belong[l] + 1, Belong[r]) res += b[i][k]; 97     id = Belong[r]; 98     rep(i, L[id], r + 1) if (Block[id][i - L[id]] == k) res++; 99     return res;100 }101 102 int main() {103     ios::sync_with_stdio(false), cin.tie(0);104     cin >> n;105     rep(i, 1, n + 1) cin >> a[i];106     init();107     int ans = 0;108     cin >> q;109     while (q--) {110         int op, l, r, k;111         cin >> op >> l >> r;112         l = (l + ans - 1) % n + 1;113         r = (r + ans - 1) % n + 1;114         if (l > r) swap(l, r);115         if (op == 1) update(l, r);116         else {117             cin >> k;118             k = (k + ans - 1) % n + 1;119             ans = query(l, r, k);120             cout << ans << endl;121         }122     }123     return 0;124 }