455D - Serega and Fun - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int s = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        ;
    for (; isdigit(c); c = getchar())
        s = s * 10 + c - '0';
    return s;
}
int n, m, a[100005], ans;
int block, L[320], R[320], bid[100005];
int cnt[320][100005];
deque<int> q[320];
void input() {
    n = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    block = sqrt(n);
    for (int i = 1; i <= block; i++)
        L[i] = R[i - 1] + 1, R[i] = i * block;
    if (R[block] < n) {
        block++;
        L[block] = R[block - 1] + 1;
        R[block] = n;
    }
    for (int i = 1; i <= block; i++)
        for (int j = L[i]; j <= R[i]; j++) {
            bid[j] = i, cnt[i][a[j]]++;
            q[i].push_back(a[j]);
        }
}
void update(int l, int r) {
    int nl = bid[l], nr = bid[r];
    if (nl == nr) {
        int x = q[nl][r - L[nl]];
        for (int i = r; i > l; i--)
            q[nl][i - L[nl]] = q[nl][i - 1 - L[nl]];
        q[nl][l - L[nl]] = x;
        return;
    }
		for (int i = bid[l] + 1; i <= bid[r]; ++i) {
	        int x = q[i - 1].back();
	        q[i - 1].pop_back(), --cnt[i - 1][x];
	        q[i].push_front(x),  ++cnt[i][x];
	    }
	    int x = q[bid[r]][r - L[bid[r]] + 1];
	    q[bid[r]].erase(q[bid[r]].begin() + (r - L[bid[r]]) + 1), --cnt[bid[r]][x];
    q[bid[l]].insert(q[bid[l]].begin() + (l - L[bid[l]]), x);
    cnt[nl][x]++;
}
inline int query(int l, int r, int k) {
	int res = 0;
	
	if (bid[l] == bid[r]) {
		for (int i = l; i <= r; ++i)
			res += (q[bid[l]][i - L[bid[l]]] == k);
	} else {
		for (int i = l; i <= R[bid[l]]; ++i)
			res += (q[bid[l]][i - L[bid[l]]] == k);
			
		for (int i = bid[l] + 1; i < bid[r]; ++i)
			res += cnt[i][k];
		
		for (int i = L[bid[r]]; i <= r; ++i)
			res += (q[bid[r]][i - L[bid[r]]] == k);
	}
	
	return res;
}
void solve() {
    m = read();
    while (m--) {
        int op = read(), l = (read() + ans - 1) % n + 1,
            r = (read() + ans - 1) % n + 1;
        if (l > r)
            swap(l, r);
        if (op == 1)
            update(l, r);
        else {
            int k = (read() + ans - 1) % n + 1;
            ans = query(l, r, k);
            printf("%d\n", ans);
        }
    }
}
int main() {
    input();
    solve();
    return 0;
}