听同机房大佬sky说这是平衡树好题，再加上本蒟蒻刚刚学习平衡树，所以写个题解加深记忆。
Solution
我们看见一操作是移动操作(连个修改都没有)，可以想到拿平衡树进行维护整个序列，这是很显然的。
然后看二操作，询问区间某个数的出现次数。
好像我所学过的平衡树是没有这种技能的（可能是我太菜没听说），本想去看看数据范围是不是除了平衡树还有别的啥，发现 (k_ileq n) ，那么可以拿 (n) 棵平衡树去维护相同值的元素的相对位置。
现在就可以说点关于这 (n+1) 棵平衡树的事了。
我们设 (t_0) 为维护整个序列的平衡树， (t_i) 是值为 (i) 的元素所在的平衡树，他们的 (key) 是这个元素在序列中的位置。
维护 (t_0) 就用正常的操作，但维护 (t_i) 是需要找到位置不超过/不小于给定值的最靠右/最靠左元素，这个是需要给定值在原序列中的位置，即 (t_0) 中的位置，所以还需要记录 (t_i) 的点在 (t_0) 中的对应点。
时间复杂度： (O(n+mlog n))
注：作者使用 (splay) ，并且不会使用指针，所以拿的结构体。码风丑陋见谅。
代码
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e5+10;
int rt[N],cnt,b[N],bel[N],lans,n,m;
struct node{
int fa,siz,val;
int son[2];
}tr[N];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
inline bool which_son(int x){
return x==tr[tr[x].fa].son[1];
}
inline void pushup(int x){
tr[x].siz=tr[tr[x].son[0]].siz+tr[tr[x].son[1]].siz+1;
}
int newnode(int f,int x){
tr[x].siz=1;
tr[x].son[0]=tr[x].son[1]=0;
tr[x].fa=f;
return x;
}
inline void rotate(int x){
int f=tr[x].fa,ff=tr[f].fa;
bool w=which_son(x);
tr[f].son[w]=tr[x].son[w^1];
tr[tr[x].son[w^1]].fa=f;
tr[x].fa=ff;
tr[x].son[w^1]=f;
tr[f].fa=x;
if(ff){
tr[ff].son[tr[ff].son[1]==f]=x;
}
pushup(f);pushup(x);
}
inline void splay(int x,int goal){
for(int f;(f=tr[x].fa)!=goal;){
if(tr[f].fa!=goal){
rotate(which_son(x)==which_son(f)?f:x);
}
rotate(x);
}
if(goal==0){
rt[bel[x]]=x;
}
}
inline void insert(int f,int p,int x){
if(!f) rt[bel[x]]=newnode(0,x);
else{
tr[f].son[p]=newnode(f,x);
splay(x,0);
}
}
int find(int x,int k){ //排名为k的编号
if(!x||tr[x].siz<k) return 0;
while(x){
if(k==tr[tr[x].son[0]].siz+1) break;
if(k>tr[tr[x].son[0]].siz+1) k-=tr[tr[x].son[0]].siz+1,x=tr[x].son[1];
else x=tr[x].son[0];
}
return x;
}
inline int pre(int x){
int now=tr[x].son[0];
while(tr[now].son[1]) now=tr[now].son[1];
return now;
}
inline int nxt(int x){
int now=tr[x].son[1];
while(tr[now].son[0]) now=tr[now].son[0];
return now;
}
inline void del(int &r,int x){
int q=pre(r),p=nxt(r);
if(!q&&!p){
r=0;return ;
}
if(!q){
splay(p,0);
tr[p].son[0]=0;
pushup(p);
return ;
}
if(!p){
splay(q,0);
tr[q].son[1]=0;
pushup(q);
return ;
}
splay(q,0);splay(p,q);
tr[p].son[0]=0;
pushup(p);pushup(q);
}
int ans;
inline int s_ize(int x){
x-=n;
splay(x,0);
return tr[tr[x].son[0]].siz+1;
}
inline void _pre(int x,int lim){ //不小于最靠左
if(!x) return ;
while(x){
if(s_ize(x)>=lim) ans=x,x=tr[x].son[0];
else x=tr[x].son[1];
}
}
inline void _nxt(int x,int lim){ //不大于最靠右
if(!x) return ;
while(x){
if(s_ize(x)<=lim) ans=x,x=tr[x].son[1];
else x=tr[x].son[0];
}
}
inline void change(int k,int k1){
splay(k,0);
del(rt[bel[k]],k);
splay(k1,0);
if(tr[tr[k1].son[0]].siz==0) insert(k1,0,k);
else{
int q=pre(rt[bel[k1]]);
splay(q,k1);insert(q,1,k);
}
}
inline void moving(int l,int r){
if(l==r) return ;
int k=find(rt[0],r),k1=find(rt[0],l);
change(k,k1);
ans=0;
_pre(rt[tr[k].val],l);
if(ans==k+n) return ;
change(k+n,ans);
}
inline void query(int l,int r,int k){
int t=lower_bound(b+1,b+n+1,k)-b;
if(!rt[t]||b[t]!=k){
printf("%d
",lans=0);
return ;
}
k=t;
int k1,k2;ans=0;
_pre(rt[k],l),k1=ans,ans=0;
_nxt(rt[k],r),k2=ans,ans=0;
if(k1==k2&&k1){
puts("1");lans=1;
}
else if(!k1||!k2||s_ize(k1)>s_ize(k2)){
puts("0");lans=0;
}
else{
splay(k1,0);splay(k2,k1);
printf("%d
",lans=tr[tr[k2].son[0]].siz+2);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)
tr[i].val=read(),b[i]=tr[i].val;
sort(b+1,b+n+1);
// cnt=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++)
tr[i].val=lower_bound(b+1,b+n+1,tr[i].val)-b;
for(int i=1;i<=n;i++)
bel[i]=0,insert(rt[0],1,i);
for(int i=1;i<=n;i++)
bel[i+n]=tr[i].val,insert(rt[tr[i].val],1,i+n);
m=read();
for(int i=1,op,l,r,k;i<=m;i++){
op=read(),l=read(),r=read();
l=(l+lans-1)%n+1,r=(r+lans-1)%n+1;
if(l>r) swap(l,r);
if(op==1) moving(l,r);
else k=(read()+lans-1)%n+1,query(l,r,k);
}
return 0;
}
本题分块做法不再说明(￣▽￣)"