此题暴力可过。
按照题意模拟即可。
注意要用 C++20。
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,a[N],lst,q;
signed main(){
std::ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>q;
for(int i=1;i<=q;i++){
int o,l,r;cin>>o>>l>>r;
l=(l+lst-1)%n+1;r=(r+lst-1)%n+1;
if(l>r) swap(l,r);
if(o==1){
int x=a[r];
for(int i=r;i^l;--i) a[i]=a[i-1];
a[l]=x;
}else{
int k;cin>>k;k=(k+lst-1)%n+1;int cnt=0;
for(int i=l;i<=r;i++) cnt+=(a[i]==k);
cout<<(lst=cnt)<<'\n';
}
}
}
上面纯属娱乐。
题解区里好像只有一篇平衡树的题解，剩下的包括 CF 官方题解都是分块，那蒟蒻就贡献一发 FHQ-Treap 的题解吧。
显然，如果不强制在线，每个颜色维护个 vector 然后二分即可。
不难发现，每次操作 1 都只影响到了 \(a_r\) 的相对位置。
考虑用平衡树维护。
用 \(n+1\) 棵平衡树，其中一棵平衡树维护相对顺序编号，\(n\) 个平衡树维护每种颜色。
时间复杂度：\(O(n + q \log_2 n)\)。
思路不难想，代码比较复杂，具体可参考下面的代码。
// I forgot all the tragedies and all I saw were miracles.
/************************************
|* Author: A.I.skeleton
|* Problem: D. Serega and Fun
|* Contest: Codeforces Round #260 (Div. 1)
|* URL: https://codeforces.com/contest/455/problem/D
|* When: 2022-11-18 18:10:31
|*
|* Memory: 256 MB
|* Time: 4000 ms
************************************/
#include <bits/stdc++.h>
using namespace std;
#define me(t,x) memset(t,x,sizeof(t))
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define R(i,j,k) for(int (i)=(j);i>=(k);(i)--)
#define FST ios::sync_with_stdio(false);cin.tie(nullptr);
namespace IO{
template<class A,class B>ostream&operator<<(ostream&X,const pair<A,B>&p)
{return X<<"{"<<F(p)<<","<<S(p)<<"}";}
template<class A>ostream&operator<<(ostream&X,const set<A>&v)
{X<<"{";for(auto i:v){if(i!=*v.begin()) X<<",";X<<i;}return X<<"}";}
template<class A,class B>ostream&operator<<(ostream&X,const map<A,B>&v)
{X<<"{";for(auto i:v){if(i!=*v.begin()) X<<",";X<<i;}return X<<"}";}
template<class A>ostream&operator<<(ostream&X,const vector<A>&v)
{X<<"{";L(i,0,si(v)-1){if(i)X<<",";X<<v[i];}return X<<"}";}
template<typename T>void rd(T &x){cin>>x;}template<typename T>void wr(T x){cout<<x;}
template<typename T,typename ...Args>void rd(T &x,Args&...g){rd(x),rd(g...);}
template<typename T,typename ...Args>void wr(T x,Args...g){wr(x),wr(g...);}
}using namespace IO;char x_x;clock_t S;
const int N=1e6,INF=1e9;
int n,q,cnt,lst,rt[N],a[N],id[N];
int pr[N],fa[N],val[N],ls[N],rs[N],si[N];
void pp(int p){si[p]=si[ls[p]]+si[rs[p]]+1;}
int nd(int v,int p=++cnt){val[p]=v;pr[p]=rand();si[p]=1;return p;}
int rk(int p){
int s=si[ls[p]]+1;for(;p^rt[0];p=fa[p])
s+=(rs[fa[p]]==p)*(si[ls[fa[p]]]+1);return s;
}void sps(int p,int v,int &x,int &y,int a,int b){
if(!p) return x=y=0,void();
if(si[ls[p]]+1<=v) fa[p]=a,sps(rs[x=p],v-si[ls[p]]-1,rs[p],y,p,b);
else fa[p]=b,sps(ls[y=p],v,x,ls[p],a,p);pp(p);
}void spv(int p,int v,int &x,int &y,int a,int b){
if(!p) return x=y=0,void();
if(rk(val[p])<=v) fa[p]=a,spv(rs[x=p],v,rs[p],y,p,b);
else fa[p]=b,spv(ls[y=p],v,x,ls[p],a,p);pp(p);
}int mer(int x,int y){
if(!x||!y) return x|y;if(pr[x]>pr[y]) return fa[rs[x]=mer(rs[x],y)]=x,pp(x),x;
else return fa[ls[y]=mer(x,ls[y])]=y,pp(y),y;
}void bud(int &p,int f,int l,int r){
if(l>r) return p=0,void();int m=(l+r)>>1;fa[id[m]=p=nd(a[m])]=f;
bud(ls[p],p,l,m-1);bud(rs[p],p,m+1,r);pp(p);
}void ins(int r,int v){int x,y;spv(rt[r],rk(v)-1,x,y,0,0);rt[r]=mer(mer(x,nd(v)),y);}
void del(int r,int v){int x,y,z;spv(rt[r],v-1,x,y,0,0);spv(y,v,y,z,0,0);rt[r]=mer(x,z);}
void spl(int l,int r){
int w,x,y,z,pre;sps(rt[0],r-1,x,y,0,0);sps(y,1,y,z,0,0);
pre=y;rt[0]=mer(mer(x,y),z);del(val[pre],r);
sps(rt[0],l-1,w,x,0,0);sps(x,r-l,x,y,0,0);sps(y,1,y,z,0,0);
rt[0]=mer(mer(mer(w,y),x),z);ins(val[pre],pre);
}int ask(int p,int l,int r){
int x,y,z,s;spv(rt[p],l-1,x,y,0,0);spv(y,r,y,z,0,0);
s=si[y];rt[p]=mer(mer(x,y),z);return s;
}char y_y;signed main(){
rd(n);L(i,1,n) rd(a[i]);
bud(rt[0],0,1,n);L(i,1,n) ins(a[i],id[i]);
rd(q);L(i,1,q){
int o,l,r,k;rd(o,l,r);l=(l+lst-1)%n+1;r=(r+lst-1)%n+1;if(l>r) swap(l,r);
if(o==1&&l<r) spl(l,r);if(o==2) rd(k),k=(k+lst-1)%n+1,wr(lst=ask(k,l,r),'\n');
}return 0;
}
卡常后排到了次优解，最优解是替罪羊树。
标签：rt,return,int,void,si,mer,CF445D From： https://www.cnblogs.com/AIskeleton/p/16904913.html