原题链接
题意：
给定长度为N(N<=100000)的序列，支持两种操作：
1 l r 将区间l到r依次向右移动一位，a[r]移动到 [l]
2 l r k 询问区间l到r中k出现次数。
强制在线
思路：
考虑操作1对操作2的影响，分块后每次移动的时候，只有首项跟尾项元素会对答案产生影响。对每个块多加个deque维护一下。
由于1 < = a i < = n，对每个数都记录一下出现的次数，还要维护c [ i ] [ j ]表示第i块里j出现的次数；
更新的时候，注意处理整块与非整块的关系
代码：
// Problem: CF455D Serega and Fun // Contest: Luogu // URL: https://www.luogu.com.cn/problem/CF455D // Memory Limit: 250 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void out(ll x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) out(x / 10); putchar(x % 10 + '0'); } inline void write(ll x){ if (x < 0) x = ~x + 1, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll p) { ll res = 1; while(b) { if(b & 1)res = res * a%p ; a = a * a %p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; const int maxn=1e5+7,maxm=210000; int n,c[360][maxn]; deque<int>a[maxn]; int num,block,belong[maxn],l[maxn],r[maxn]; int ans=0; void cul(int &x){ x=(x+ans-1)%n+1; } void update(int l,int r){ int bl=l/block,br=r/block; if(bl==br){ r=r%block-1; int x=a[br][r]; a[br].erase(a[br].begin()+r); a[bl].insert(a[bl].begin()+l%block,x); } else{ int x; for(int i=bl;i<br;){ x=a[i].back();a[i].pop_back();c[i][x]--; i++; a[i].push_front(x);c[i][x]++; } r%=block;x=a[br][r]; a[br].erase(a[br].begin()+r);c[br][x]--; a[bl].insert(a[bl].begin()+l%block,x);c[bl][x]++; } } int query(int l,int r,int k){ int an=0; int bl=l/block,br=r/block; if(bl==br){ for(int i=l%block;i<r%block;i++) if(a[bl][i]==k) an++; } else{ for(int i=bl+1;i<br;i++) an+=c[i][k]; for(int i=l%block;i<a[i].size();i++) if(a[bl][i]==k) an++; for(int i=0;i<r%block;i++) if(a[br][i]==k) an++; } return an; } int main(){ n=read; block=int(sqrt(n)); rep(i,0,n-1){ int x=read; a[i/block].push_back(x); c[i/block][x]++; } int q=read; while(q--){ int op=read,l=read,r=read; cul(l);cul(r); if(l>r) swap(l,r); l--; if(op==1) update(l,r); else{ int k=read;cul(k); ans=query(l,r,k); printf("%d\n",ans); } } return 0; }
