题意：给你一列数，只会有询问操作，询问区间l，r中的众数是几，如果有多个众数，打印最小的那个
思路：的确不怎么会，一开始想到维护块内的众数，但是如果一个块中有很多众数就不知道该怎么办了，看了hzw聚聚的博客以后才知道，我们对于整块，可以提前n2预处理出答案，然后对于不是整块的，我们直接暴力求解就可以了
代码：在洛谷不开氧气过不去啊（为什么写的这么丑）
#include <bits/stdc++.h> using namespace std; typedef long long LL; inline LL read() { LL x=0,f=1;char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int n,m; int block,id; int a[50005],belong[50005]; int f[505][505]; map<int,int>mp; int val[50005],cnt[50005]; vector<int>p[50005]; void solve(int x) { memset(cnt,0,sizeof(cnt)); int maxe=0,ans=0; for(int i=(x-1)*block+1;i<=n;i++){ cnt[a[i]]++; if(cnt[a[i]]>maxe||(cnt[a[i]]==maxe&&val[a[i]]<val[ans])) ans=a[i],maxe=cnt[a[i]]; f[x][belong[i]]=ans; } } int query(int l,int r,int x) { int res=upper_bound(p[x].begin(),p[x].end(),r)- lower_bound(p[x].begin(),p[x].end(),l); return res; } int query(int l,int r) { int ans,maxe; ans=f[belong[l]+1][belong[r]-1]; maxe=query(l,r,ans); for(int i=l;i<=min(belong[l]*block,r);i++){ int res=query(l,r,a[i]); if(res>maxe||(res==maxe&&val[a[i]]<val[ans])) maxe=res,ans=a[i]; } if(belong[l]!=belong[r]){ for(int i=block*(belong[r]-1)+1;i<=r;i++){ int res=query(l,r,a[i]); if(res>maxe||(res==maxe&&val[a[i]]<val[ans])) maxe=res,ans=a[i]; } } return ans; } int main() { n=read();m=read(); block=sqrt(n); int ans=0; for(int i=1;i<=n;i++){ a[i]=read(); if(mp[a[i]]==0){ mp[a[i]]=++id; val[id]=a[i]; } a[i]=mp[a[i]]; p[a[i]].push_back(i); } for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1; for(int i=1;i<=belong[n];i++)solve(i); for(int i=1;i<=m;i++){ int l=read(),r=read(); l=(l+ans-1)%n+1;r=(r+ans-1)%n+1; if(l>r)swap(l,r); ans=val[query(l,r)]; printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/lalalatianlalu/p/9875251.html