首先用 map 离散化，首先预处理一下每个块内的众数，同时我们要把每个数出现的位置 push 到以这个数为下标的 vector 里。这样我们查询某一个区间内这个数的个数，只需要这样即可：
inline int getcnt(int l,int r,int x){ return upper_bound(b[x].begin(),b[x].end(),r)-lower_bound(b[x].begin(),b[x].end(),l); }这样散点我们就能暴力统计了。大块直接取 \(\max\)。
#pragma GCC optimize(2) #include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+10; int n,m,S; int a[maxn]; char buf[1<<20],*p1,*p2; #define gc() (p1==p2?(p2=buf+fread(p1=buf,1,1<<20,stdin),p1==p2?EOF:*p1++):*p1++) inline int read(){ int x=0;bool fopt=1;char ch=gc(); for(;!isdigit(ch);ch=gc())if(ch=='-')fopt=0; for(;isdigit(ch);ch=gc())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } int id; int belong[maxn],L[maxn],R[maxn],v[maxn],cnt[maxn]; unordered_map<int,int> mp; vector<int> b[maxn]; inline void Init(){ for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; if(mp[a[i]]==0){ mp[a[i]]=++id;v[id]=a[i];//同时还要记录原来该数是什么 } a[i]=mp[a[i]]; b[a[i]].push_back(i);//push下标进去 } } int f[500+10][500+10];//预处理块最小众数 void Prework(int x){ memset(cnt,0,sizeof(cnt)); int Max=0,ans=0; for(int i=L[x];i<=n;i++){ int temp=++cnt[a[i]]; if(temp>Max||temp==Max&&v[a[i]]<v[ans]){ Max=temp; ans=a[i]; } f[x][belong[i]]=ans; } } inline int getcnt(int l,int r,int x){ return upper_bound(b[x].begin(),b[x].end(),r)-lower_bound(b[x].begin(),b[x].end(),l); } inline int Solve(int l,int r){ int ans=f[belong[l]+1][belong[r]-1],Max=getcnt(l,r,ans); for(int i=l;i<=min(R[belong[l]],r);i++){ int temp=getcnt(l,r,a[i]); if(temp>Max||temp==Max&&v[a[i]]<v[ans]){ Max=temp;ans=a[i]; } } if(belong[l]!=belong[r]){ for(int i=L[belong[r]];i<=r;i++){ int temp=getcnt(l,r,a[i]); if(temp>Max||temp==Max&&v[a[i]]<v[ans]){ Max=temp;ans=a[i]; } } } return ans; } signed main(){ n=read();S=sqrt(n); for(int i=1;i<=n;i++) a[i]=read(); Init(); for(int i=1;i<=belong[n];i++) Prework(i); int last=0; for(int i=1;i<=n;i++){ int l=read(),r=read(); if(l>r)swap(l,r); last=v[Solve(l,r)]; printf("%lld\n",last); } return 0; }双倍经验