# Codeforces 455D Serega and Fun【解法二】 -开发者知识库

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010,maxm=320;
void init()
{
clo  ;
for (int i=1;i<=m;i  )
{
L[i]=R[i-1] 1;
R[i]=(i==m?n:L[i] m-1);
for (int j=L[i];j<R[i];j  ) next[a[j]]=a[j 1];
next[a[R[i]]]=0;
if (edi[i][val[j]]<clo)
{
edi[i][val[j]]=clo;
cnt[i][val[j]]=1;
}
else cnt[i][val[j]]  ;
}
}
void modi(int l,int r)
{
int pl,pr,u,v,x;
for (int i=1;i<=m;i  )
if (L[i]<=r&&r<=R[i])
{
pr=i;
for (int j=L[i] 1;j<=r;j  )
{
x=v;
v=next[v];
}
else next[x]=next[v];
cnt[i][val[v]]--;
}
for (int i=1;i<=m;i  )
if (L[i]<=l&&l<=R[i])
{
pl=i;
for (int j=L[i] 1;j<=l;j  )
{
x=u;
u=next[u];
}
else next[x]=v;
next[v]=u;
if (edi[i][val[v]]<clo)
{
edi[i][val[v]]=clo;
cnt[i][val[v]]=1;
}
else cnt[i][val[v]]  ;
}
if (pl<pr)
{
R[pl]  ;
L[pr]  ;
for (int i=pl 1;i<pr;i  )
L[i]  ,R[i]  ;
}
}
int qry(int l,int r,int k)
{
int ans=0,pl,pr;
for (int i=1;i<=m;i  )
{
if (L[i]<=l&&l<=R[i]) pl=i;
if (L[i]<=r&&r<=R[i]) pr=i;
}
if (pl==pr)
{
if (j>=l&&val[i]==k) ans  ;
return ans;
}
if (j>=l&&val[i]==k) ans  ;
if (val[i]==k) ans  ;
for (int i=pl 1;i<pr;i  )
if (edi[i][k]==clo) ans =cnt[i][k];
return ans;
}
int main()
{
//freopen("f.in","r",stdin);
int last=0,now=0,opt,l,r,k,t;
scanf("%d",&n);
for (int i=1;i<=n;i  ) scanf("%d",&val[i]);
m=sqrt(n);
for (int i=1;i<=n;i  ) a[i]=i;
init();
scanf("%d",&q);
while (q--)
{
scanf("%d%d%d",&opt,&l,&r);
l=(l last-1)%n 1;
r=(r last-1)%n 1;
if (l>r) swap(l,r);
if (opt==1)
{
modi(l,r);
if (  now==m)
{
t=0;
for (int i=1;i<=m;i  )
a[  t]=j;
init();
now=0;
}
}
else
{
scanf("%d",&k);
k=(k last-1)%n 1;
printf("%d\n",last=qry(l,r,k));
}
}
}

0条回复