in1
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
out1
2 1 0 0
in2
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
out2
2 0
给定一个长度为n的序列a[]，每个元素1 <= a[i] <= n, 1 <= n <= 1e5
有两种操作：
1： 将区间[l,r]内的每个元素向后循环一位，区间内最后一个元素替换到第一个元素
2： 询问区间[l,r] 内某个数val的出现次数
对于操作1：
在修改的时候，对每一个块可以维护一个双端队列，每次在移位的过程中{
1. 最左端的块最右边的元素过渡到下一个块的首部，最左端l处加入原始在r处的元素
2. 最右端的块的首部加入前一个块的最后一个元素，最右端的一个元素(原始在r处)加入到1.中描述的l处
3. 中间的整块首部加入前一个块的最后元素，后部pop出最后一个元素加入到下一个块的首部
4. 在处理的过程中记得解决预处理的个数变化pop出的时候 -1 ，push入的时候 +1
}
对于操作2：
{
在左右两端的块中，我们可以暴力求出
在中间整数块中，可以直接由预处理得到
}
写的时候细节比较多
/*** keep hungry and calm PushyTao!***/ int blk,n,a[maxn],b[maxn],c[350][maxn],R[357]; deque<int> deq[350]; int t[maxn]; /** void modify(int l,int r) { int p = 0; if(b[l] == b[r]) { // in the same depart while(deq[b[l]].size()) { t[++p] = deq[b[l]].back(); deq[b[l]].pop_back(); } l -= (b[l] - 1) * blk; r -= (b[l] - 1) * blk; int last = t[r];///the r-th elem for(int i=r; i>=l+1; i--) t[i] = t[i-1]; t[l] = last; for(int i=1; i<=p; i++) { deq[b[l]].push_front(t[i]); } return; } int last = deq[b[l]].front(); for(int i=b[l]+1; i<=b[r]-1; i++) { deq[i].push_back(last); c[i][last] ++; last = deq[i].front(); deq[i].pop_front(); c[i][last] --; } p = 0; for(int i=(b[r]-1)*blk+1; i <= r; i++) { c[b[r]][deq[b[r]].back()] --; t[++p] = deq[b[r]].back(); deq[b[r]].pop_back(); } for(int i=p-1; i>=1; i--) { c[b[r]][t[i]] ++; deq[b[r]].push_back(t[i]); } deq[b[r]].push_back(last); c[b[r]][last] ++; last = t[p]; p = 0;/// b[l] blks for(int i=l; i<=min(b[l]*blk,n); i++) { c[b[l]][deq[b[l]].front()] --; t[++p] = deq[b[l]].front(); deq[b[l]].pop_front(); } deq[b[l]].push_front(last);/// front in c[b[l]][last] ++; for(int i=p; i>=2; i--) { c[b[l]][t[i]] ++; deq[b[l]].push_front(t[i]); } } int query(int l,int r,int val) { int p = 0,ans = 0; if(b[l] == b[r]) {// in the same blk while(deq[b[l]].size()) { t[++p] = deq[b[l]].back(); deq[b[l]].pop_back(); } l -= (b[l] - 1) * blk; r -= (b[l] - 1) * blk; for(int i=l; i<=r; i++) if(t[i] == val) ans ++; for(int i=1; i<=p; i++) { deq[b[l]].push_front(t[i]); } return ans; } for(int i=b[l]+1; i<=b[r]-1; i++) { ans += c[i][val]; } p = 0; for(int i=(b[r]-1) * blk+1; i<=r; i++) { if(deq[b[r]].back() == val) ans ++; t[++p] = deq[b[r]].back(); deq[b[r]].pop_back(); } for(int i=p; i>=1; i--) { deq[b[r]].push_back(t[i]); } p = 0; for(int i=l; i<=min(b[l]*blk,n); i++) { if(deq[b[l]].front() == val) ans ++; t[++p] = deq[b[l]].front(); deq[b[l]].pop_front(); } for(int i=p; i>=1; i--) { deq[b[l]].push_front(t[i]); } return ans; } **/ void modify2(int l,int r) { if(l > r) swap(l,r); int s = b[l],e = b[r]; int p = 0; if(s == e) { while(deq[s].size()) { t[++p] = deq[s].back(); deq[s].pop_back(); } l -= (s - 1) * blk; r -= (s - 1) * blk; int pre = t[r]; for(int i=r; i>=l+1; i--) t[i] = t[i-1]; t[l] = pre; for(int i=1; i<=p; i++) deq[s].push_front(t[i]); return ;// ok } int pre = deq[s].front();/// pre push front : front = last one for(int i=s+1; i<=e-1; i++) { deq[i].push_back(pre); c[i][pre] ++;// in one elem pre = deq[i].front(); deq[i].pop_front(); c[i][pre] --; } p = 0; for(int i=(e-1)*blk+1; i<=r; i++) { c[e][deq[e].back()] --; t[++p] = deq[e].back(); deq[e].pop_back(); } for(int i=p-1; i>=1; i--) { c[e][t[i]] ++; deq[e].push_back(t[i]); } deq[e].push_back(pre); c[e][pre] ++; pre = t[p]; p = 0; for(int i=l; i<=R[s]; i++) { c[s][deq[s].front()] --; t[++p] = deq[s].front(); deq[s].pop_front(); } deq[s].push_front(pre); c[s][pre] ++; for(int i=p; i>=2; i--) { c[s][t[i]] ++; deq[s].push_front(t[i]); } } int query2(int l,int r,int val) { int ans = 0,p = 0; if(l > r) swap(l,r); int s = b[l],e = b[r];// start blk end blk if(s == e) { while(deq[s].size()) { t[++p] = deq[s].back(); deq[s].pop_back(); } l -= (s - 1) * blk; r -= (s - 1) * blk; for(int i=l; i<=r; i++) if(t[i] == val) ans ++; for(int i=1; i<=p; i++) deq[s].push_front(t[i]); return ans; } for(int i=s+1; i<=e-1; i++) ans += c[i][val]; p = 0; for(int i=(e-1)*blk + 1; i<=r; i++) { if(deq[e].back() == val) ans ++; t[++p] = deq[e].back(); deq[e].pop_back(); } for(int i=p; i>=1; i--) deq[e].push_back(t[i]); p = 0; for(int i=l; i<=R[s]; i++) { if(deq[s].front() == val) ans ++; t[++p] = deq[s].front(); deq[s].pop_front(); } for(int i=p; i>=1; i--) deq[s].push_front(t[i]); return ans; } int main() { n = read; blk = sqrt(n); for(int i=1; i<=n; i++) a[i] = read; for(int i=1; i<=n; i++) { b[i] = (i-1) / blk + 1; c[b[i]][a[i]] ++; R[b[i]] = min(b[i] * blk,n); deq[b[i]].push_front(a[i]); } int lastans = 0; int q = read; while(q --) { int op = read,l = read,r = read; l = (l + lastans - 1) % n + 1; r = (r + lastans - 1) % n + 1; if(l > r) swap(l,r); if(op == 1) { modify2(l,r); } else { int val = read; val = (val + lastans - 1) % n + 1; lastans = query2(l,r,val); printf("%d\n",lastans); } } return 0; } /** 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 **/
