题意
在线区间众数
思路
预处理出 f[i][j] 即从第 i 块到第 j 块的答案。
对于每个询问，中间的整块直接用预处理出的，两端的 sqrtn 级别的数暴力做，用二分查找它们出现的次数。
每次询问的复杂度是 sqrtn * logn 。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=;
vector<int> vec[N];
int n,m,a[N],b[N],block[N],ans,Block,L[N],R[N],cnt[N],top,stack[N],f[][],ff[][],tot;
int find1(int x,int y){
int l=;int r=vec[x].size()-;
int tmp=-;
while(l<=r){
int mid=(l+r)>>;
if(vec[x][mid]<=y){
tmp=mid;
l=mid+;
}
else r=mid-;
}
return tmp;
}
int find2(int x,int y){
int l=;int r=vec[x].size()-;
int tmp=;
while(l<=r){
int mid=(l+r)>>;
if(vec[x][mid]>=y){
tmp=mid;
r=mid-;
}
else l=mid+;
}
return tmp;
}
int main(){
scanf("%d%d",&n,&m);
Block=sqrt(n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+,b++n);
int num=unique(b+,b++n)-b-;
for(int i=;i<=n;i++){
a[i]=lower_bound(b+,b++num,a[i])-b;
block[i]=(i-)/Block+;
vec[a[i]].push_back(i);
if(!L[block[i]])L[block[i]]=i;
R[block[i]]=i;
}
for(int i=;i<=block[n];i++){
tot=;
for(int j=L[i];j<=n;j++){
cnt[a[j]]++;
if(tot<=cnt[a[j]]){
if(cnt[a[j]]>tot)ans=b[a[j]];
else ans=min(ans,b[a[j]]);
tot=cnt[a[j]];
}
f[i][block[j]]=tot;
ff[i][block[j]]=ans;
}
for(int j=L[i];j<=n;j++){
cnt[a[j]]=;
}
}
ans=;
for(int i=;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
l=(l+ans-)%n+;r=(r+ans-)%n+;
if(l>r)swap(l,r);
if(block[l]+>=block[r]){
tot=;
ans=;
for(int i=l;i<=r;i++){
cnt[a[i]]++;
if(tot<=cnt[a[i]]){
if(cnt[a[i]]>tot)ans=b[a[i]];
else ans=min(ans,b[a[i]]);
tot=cnt[a[i]];
}
}
for(int i=l;i<=r;i++){
cnt[a[i]]=;
}
}
else{
top=;
tot=f[block[l]+][block[r]-];
ans=ff[block[l]+][block[r]-];
for(int i=l;i<=R[block[l]];i++){
cnt[a[i]]++;
if(cnt[a[i]]==)stack[++top]=a[i];
}
for(int i=L[block[r]];i<=r;i++){
cnt[a[i]]++;
if(cnt[a[i]]==)stack[++top]=a[i];
}
while(top){
int z=stack[top--];
int tmp=max(,find1(z,L[block[r]]-)-find2(z,R[block[l]]+)+);
if(tot<=cnt[z]+tmp){
if(cnt[z]+tmp>tot)ans=b[z];
else ans=min(ans,b[z]);
tot=cnt[z]+tmp;
}
cnt[z]=;
}
}
printf("%d\n",ans);
}
return ;
}