https://www.luogu.com.cn/problem/P4168
分块大法好
首先离散化把值域缩小到n
预处理3个数组
sum[i][j]表示前i块里j的出现次数
mx[i][j]表示第i块到第j块出现次数最多的数出现了多少次
who[i][j]表示第i块到第j块出现次数最多的数最小是谁
对于查询
如果左右端点在同一块或者相邻,就暴力求
如果左右端点所在块中间至少隔着一块,
假设左端点在第bl块,右端点在br块
先直接通过mx和who获取bl+1到br-1块中出现次数最多的最小的数及出现次数
然后只考虑在bl块里左端点后面的,以及在br块里右端点前面的数
枚举这些数,先用一个数组记录在bl+1到br-1块中出现的次数
然后再对他们累加左右端点所在块的出现次数,更新答案
#include<bits/stdc++.h> using namespace std; #define N 50002 int a[N],ha[N]; int sum[251][N]; int mx[251][251],who[251][251]; int tmp[N]; int main() { //freopen("P4168_1.in","r",stdin); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d",&a[i]); ha[i]=a[i]; } sort(ha+1,ha+n+1); int nn=unique(ha+1,ha+n+1)-ha-1; for(int i=1;i<=n;++i) a[i]=lower_bound(ha+1,ha+nn+1,a[i])-ha; int siz=sqrt(n),s=(n-1)/siz+1,rr,rr2; for(int i=1;i<=s;++i) { for(int j=1;j<=nn;++j) { sum[i][j]=sum[i-1][j]; tmp[j]=0; } for(int j=1;j<i;++j) { mx[j][i]=mx[j][i-1]; who[j][i]=who[j][i-1]; } rr=min(n,i*siz); for(int j=(i-1)*siz+1;j<=rr;++j) { sum[i][a[j]]++; for(int k=1;k<=i;++k) { rr2=siz*k; if(sum[i][a[j]]-sum[k-1][a[j]]>mx[k][i] || sum[i][a[j]]-sum[k-1][a[j]]==mx[k][i] && a[j]<who[k][i]) { mx[k][i]=sum[i][a[j]]-sum[k-1][a[j]]; who[k][i]=a[j]; } } } } int l,r,bl,br,amx,awho,last=0; while(m--) { scanf("%d%d",&l,&r); l=(l+last-1)%n+1; r=(r+last-1)%n+1; if(l>r) swap(l,r); bl=(l-1)/siz+1; br=(r-1)/siz+1; if(bl+1>=br) { amx=0; for(int i=l;i<=r;++i) tmp[a[i]]=0; for(int i=l;i<=r;++i) { tmp[a[i]]++; if(tmp[a[i]]>amx || tmp[a[i]]==amx && a[i]<awho) { amx=tmp[a[i]]; awho=a[i]; } } } else { amx=mx[bl+1][br-1]; awho=who[bl+1][br-1]; rr=bl*siz; rr2=(br-1)*siz+1; for(int i=l;i<=rr;++i) tmp[a[i]]=sum[br-1][a[i]]-sum[bl][a[i]]; for(int i=rr2;i<=r;++i) tmp[a[i]]=sum[br-1][a[i]]-sum[bl][a[i]]; for(int i=l;i<=rr;++i) { tmp[a[i]]++; if(tmp[a[i]]>amx || tmp[a[i]]==amx && a[i]<awho) { amx=tmp[a[i]]; awho=a[i]; } } for(int i=rr2;i<=r;++i) { tmp[a[i]]++; if(tmp[a[i]]>amx || tmp[a[i]]==amx && a[i]<awho) { amx=tmp[a[i]]; awho=a[i]; } } } last=ha[awho]; printf("%d\n",last); } }