haooo @ 2020-07-22 16:01:15
#include<bits/stdc++.h>
using namespace std;
#define RT register
const int MAXN=40005;
int n,m,t;//n表示长度,m表示询问个数,t表示块数
int R[205],L[205]; //表示每个块的左边界与右边界
int a[MAXN];//每个蒲公英的种类,里面存的是hash值
int fh[MAXN];//反hash数组,存hash值所代表的真实种类
int pos[MAXN];//每个蒲公英在第几块
int pre[205][MAXN];//前缀和,pre[i][j]表示前i块,种类j的个数
int cnt;//种类的总数(有多少种蒲公英)
unordered_map <int,int> ha;//
inline int read(){//快读
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=10*s+ch-'0',ch=getchar();
return s*w;
}
int h(int x){//离散化,我用的是unordered_map
if(ha.count(x)) return ha[x];//已经出现过
fh[++cnt]=x;//没有出现过,cnt++
return ha[x]=cnt;//返回hash值
}
int ask(int l,int r){//询问函数
int ans=0;
int p=pos[l],q=pos[r];//l所在的块与r所在的块
if(p==q||p+1==q){//相临,直接暴力
int vis[MAXN]={};//记录出现次数
for(RT int i=l;i<=r;i++) vis[a[i]]++; //暴力从左到右依次扫描
int maxn=0;//最大值
for(RT int i=1;i<=cnt;i++){//暴力比较
if(vis[i]>maxn||(fh[i]<fh[ans]&&vis[i]==maxn)){ //如果当前数量大于最大值
// 或者等于当前最大值种类序号小与当前最大种类序号
maxn=vis[i];//更改最大值
ans=i;//更改答案
}
}
}
else{//相隔大于一块
// cout<<2<<"\n";
int vis[MAXN]={};//记录出现次数
for(RT int i=l;i<=R[p];i++) vis[a[i]]++;//当前种类数目+1
for(RT int i=L[q];i<=r;i++) vis[a[i]]++;//当前种类数目+1
for(RT int i=1;i<=cnt;i++) vis[i]+=pre[q-1][i]-pre[p][i];//暴力每一个种类,加上区间和
int maxn=0;//最大值
for(RT int i=1;i<=cnt;i++){//爆力扫描一遍
// cout<<fh[i]<<" "<<vis[i]<<"\n";
if(vis[i]>maxn||(fh[i]<fh[ans]&&vis[i]==maxn)){//如果当前数量大于最大值
// 或者等于当前最大值种类编号小与当前最大种类编号
maxn=vis[i];//更改最大值
ans=i;//更改答案
}
}
}
return ans;
}
int main(){
//freopen("P4168.in","r",stdin);
//freopen("my.out","w",stdout);
n=read();m=read();//输入n,m
int kkk;//一个变量,记录当时输入的原种类编号
for(RT int i=1;i<=n;i++){//输入a[i]
kkk=read();
a[i]=h(kkk);//以hash值存入
}
t=sqrt(n);
for(RT int i=1;i<=t;i++){//处理左边界与右边界
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]!=n){//右边还有一部分还未入块
L[++t]=R[t-1]+1;
R[t]=n;
}
for(RT int i=1;i<=t;i++){//循环每个块
for(RT int j=L[i];j<=R[i];j++){//暴力扫描
pos[j]=i;//位置
for(RT int k=i;k<=t;k++) pre[k][a[j]]++;//预处理前缀和
}
}
int x=0;
fh[0]=40005;//使ans初始的反hash最大
while(m--){
int l,r;
int lo,ro;
lo=read();ro=read();//输入
l=((lo+x-1)%n)+1;//解密
r=((ro+x-1)%n)+1;
if(l>r) swap(l,r);//交换
x=fh[ask(l,r)];//x赋值
printf("%d\n",x);//输出
}
return 0;
}
75分
错了前五个点
by 1saunoya @ 2020-07-22 16:07:11
数据结构自己调。。。
by 1saunoya @ 2020-07-22 16:07:24
这种题不会有人来帮你调的.jpg
by haooo @ 2020-07-22 16:32:48
(
by Remake_ @ 2020-09-24 22:25:20
qndmbt