考虑分块做法。
我们以 \(\sqrt{n}\) 为块长分块,套路地维护每个数在这个每块中的出现次数 \(cnt\)。
对于 2 操作,整块直接读取 \(cnt\),其余的直接暴力查询。
对于 1 操作,如果在同一个块里,直接暴力去做。如果不在,我们就将最后一个元素插入第一个元素所在的块中,然后整块平移并更新 \(cnt\) 的值,此过程需要用 deque 维护。
特别注意:dq[belong[r]].erase(dq[belong[r]].begin()+r-lx[r]);
会导致 RE,把 r-lx[r]
括起来即可。
/*
* Title: Serega and Fun
* Source: 洛谷-CF
* URL: https://www.luogu.com.cn/problem/CF455D
* Author: Steven_lzx
* Command: -std=c++23 -Wall -fno-ms-extensions
* Date: 2022.11.3
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,t,num,a[MAXN],cnt[350][MAXN],belong[MAXN],ans,q,lx[MAXN],rx[MAXN];
deque<int> dq[350];
int main()
{
int op,l,r,k,temp;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
t=max(3,(int)sqrt(n));
num=ceil(n*1.0/t);
for(int i=1;i<=num;i++)
{
for(int j=(i-1)*t+1;j<=min(n,i*t);j++)
{
belong[j]=i;
lx[j]=(i-1)*t+1;
rx[j]=min(n,i*t);
}
}
/*for(int i=1;i<=n;i++)
cout<<belong[i]<<' '<<lx[i]<<' '<<rx[i]<<endl;*/
for(int i=1;i<=n;i+=t)
{
for(int j=lx[i];j<=rx[i];j++)
{
dq[belong[i]].push_back(a[j]);
cnt[belong[i]][a[j]]++;
}
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&l,&r);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
if(l>r)
swap(l,r);
if(belong[l]==belong[r])
{
temp=dq[belong[l]][r-lx[l]];
dq[belong[l]].erase(dq[belong[l]].begin()+(r-lx[l]));//必须加括号,否则 RE,下同
dq[belong[l]].insert(dq[belong[l]].begin()+(l-lx[l]),temp);
}
else
{
dq[belong[l]].insert(dq[belong[l]].begin()+(l-lx[l]),dq[belong[r]][r-lx[r]]);
cnt[belong[l]][dq[belong[r]][r-lx[r]]]++;
cnt[belong[r]][dq[belong[r]][r-lx[r]]]--;
dq[belong[r]].erase(dq[belong[r]].begin()+(r-lx[r]));
for(int i=belong[l]+1;i<=belong[r];i++)
{
temp=dq[i-1].back();
dq[i-1].pop_back();
cnt[i-1][temp]--;
dq[i].push_front(temp);
cnt[i][temp]++;
}
}
}
else
{
scanf("%d%d%d",&l,&r,&k);
l=(l+ans-1)%n+1;
r=(r+ans-1)%n+1;
k=(k+ans-1)%n+1;
if(l>r)
swap(l,r);
ans=0;
function<int(int,int,int)> answer=[&](int l,int r,int k)
{
int res=0;
if(belong[l]==belong[r])
{
for(int i=l;i<=r;i++)
if(dq[belong[l]][i-lx[l]]==k)
res++;
}
else
{
res+=answer(l,rx[l],k);
for(int i=belong[l]+1;i<belong[r];i++)
res+=cnt[i][k];
res+=answer(lx[r],r,k);
}
return res;
};
printf("%d\n",ans=answer(l,r,k));
}
}
return 0;
}
原文地址:http://www.cnblogs.com/2020gyk080/p/16855668.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性