先填个坑 有时间再去看CLJ的题解 CLJ题解里有这样的一个定理
令 mode(S) 为可重集合 S 的众数 mode(A⋃B)∈mode(A)⋃B 证明 如果 t∉mode(A)⋃B 那么 t 在 mode(A⋃B)中的出现次数就是在 A 中出现的次数 不会多于mode(A)
把序列分成 n√ 块 那么我们就可以利用这个定理预处理出 任意两块之间的众数 询问时就是比较连续的整块的众数和剩余的数出现次数 如果直接用二分来查找一个数 x 在区间[l,r]中出现的次数 复杂度 O(nn√logn) 如果用分块预处理 花费空间换时间 可以做到 O(1) 询问出现次数 那么就是 O(nn√) 人懒没办法
#include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=40005; int sx[N],icnt; inline int Bin(int x){ return lower_bound(sx+1,sx+icnt+1,x)-sx; } vector<int> ps[N]; inline int Find(int i,int l,int r){ return upper_bound(ps[i].begin(),ps[i].end(),r)-lower_bound(ps[i].begin(),ps[i].end(),l); } #define Pair(x,l,r) (abcd(Find(x,l,r),x)) struct abcd{ int first,second; abcd(int x=0,int y=0):first(x),second(y) { } bool operator < (const abcd &B) const{ return first==B.first?second>B.second:first<B.first; } }; const int B=205; int n,a[N]; int Blo; int pos[N]; int lp[B],rp[B],tot; abcd mode[B][B]; inline int Query(int l,int r){ int lb=pos[l],rb=pos[r]; abcd ret=abcd(0,0); if (lb==rb){ for (int i=l;i<=r;i++) ret=max(ret,Pair(a[i],l,r)); return sx[ret.second]; } if (lb+1<=rb-1) ret=Pair(mode[lb+1][rb-1].second,l,r); for (int i=l;i<=rp[lb];i++) ret=max(ret,Pair(a[i],l,r)); for (int i=lp[rb];i<=r;i++) ret=max(ret,Pair(a[i],l,r)); return sx[ret.second]; } int main(){ int Q,lastans=0,l,r; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(Q); for (int i=1;i<=n;i++) read(a[i]),sx[++icnt]=a[i]; sort(sx+1,sx+icnt+1); icnt=unique(sx+1,sx+icnt+1)-sx-1; for (int i=1;i<=n;i++) a[i]=Bin(a[i]),ps[a[i]].push_back(i); Blo=sqrt(n); for (int i=1;i<=n;i++) pos[i]=(i-1)/Blo+1; tot=pos[n]; for (int i=1;i<=tot;i++) lp[i]=Blo*(i-1)+1,rp[i]=Blo*i; rp[tot]=n; for (int i=1;i<=tot;i++) for (int j=i;j<=tot;j++){ mode[i][j]=abcd(0,0); if (i<j) mode[i][j]=Pair(mode[i][j-1].second,lp[i],rp[j]); for (int k=lp[j];k<=rp[j];k++) mode[i][j]=max(mode[i][j],Pair(a[k],lp[i],rp[j])); } while (Q--){ read(l); read(r); l=(l+lastans-1)%n+1; r=(r+lastans-1)%n+1; if (l>r) swap(l,r); printf("%d\n",lastans=Query(l,r)); } return 0; }