数据结构：分块-区间众数查询

这里只支持查询不支持修改，总的时间复杂度为O（(n+q)*√n）
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 using namespace std;
  5 const int maxn=100005;
  6 int n,m,blo;
  7 int a[maxn],t[maxn],bl[maxn];
  8 int cnt[505][maxn],f[505][505];
  9 //cnt[i][j]表示[0,i]块上数字j的数量
 10 //f[i][j]表示第i块到第j块的众数是几
 11 inline long long read()
 12 {
 13     long long x=0,f=1;char ch=getchar();
 14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 16     return x*f;
 17 }
 18 void init()
 19 {
 20     for(int i=1;i<=bl[n];i++)
 21     {
 22         for(int j=1;j<=m;j++)
 23             cnt[i][j]+=cnt[i-1][j];
 24     }
 25     for(int i=1;i<=bl[n];i++)
 26     {
 27         int num[maxn];
 28         int mode=0;
 29         int mx=0;
 30         for(int k=1;k<=m;k++) num[k]=0;
 31         for(int j=(i-1)*blo+1;j<=n;j++)
 32         {
 33             num[a[j]]++;
 34             if(num[a[j]]>mx||(num[a[j]]==mx&&mode>a[j]))
 35             {
 36                 mode=a[j];
 37                 mx=num[a[j]];
 38             }
 39             f[i][bl[j]]=mode;
 40         }
 41     }
 42 }
 43 void force(int l,int r)
 44 {
 45     int num[maxn];
 46     int mode=0;
 47     int mx=0;
 48     for(int i=1;i<=m;i++) num[i]=0;
 49     for(int i=l;i<=r;i++)
 50     {
 51         num[a[i]]++;
 52         if(num[a[i]]>mx||(num[a[i]]==mx&&mode>a[i]))
 53         {
 54             mode=a[i];
 55             mx=num[a[i]];
 56         }
 57     }
 58     printf("%d
",t[mode]);
 59 }
 60 void solve(int t1,int t2,int l,int r,int *num,int &mode,int &mx)
 61 {
 62     for(int i=l;i<=r;i++)
 63     {
 64         num[a[i]]++;
 65         int tmp=num[a[i]]+cnt[t2-1][a[i]]-cnt[t1][a[i]];
 66         if(tmp>mx||(tmp==mx&&a[i]<mode))
 67         {
 68             mode=a[i];
 69             mx=tmp;
 70         }
 71     }
 72 }
 73 void query(int l,int r)
 74 {
 75     int t1=bl[l];
 76     int t2=bl[r];
 77     if(t1==t2||t1+1==t2)
 78     {
 79         force(l,r);
 80         return;
 81     }
 82     int mode=f[t1+1][t2-1];
 83     int mx=cnt[t2-1][mode]-cnt[t1][mode];
 84     int num[maxn];
 85     for(int i=1;i<=m;i++) num[i]=0;
 86     int L=l,R=t1*blo;
 87     solve(t1,t2,L,R,num,mode,mx);
 88     L=(t2-1)*blo+1;
 89     R=r;
 90     solve(t1,t2,L,R,num,mode,mx);
 91     printf("%d
",t[mode]);
 92 }
 93 int main()
 94 {
 95     n=read();
 96     blo=2*sqrt(n);
 97     for(int i=1;i<=n;i++)
 98     {
 99         a[i]=read();
100         t[i]=a[i];
101         bl[i]=(i-1)/blo+1;
102     }
103     sort(t+1,t+n+1);
104     m=unique(t+1,t+n+1)-t-1;  //去重
105     for(int i=1;i<=n;i++)
106     {
107         a[i]=lower_bound(t+1,t+m+1,a[i])-t;
108         cnt[bl[i]][a[i]]++;
109     }
110     init();
111     for(int i=1;i<=n;i++)
112     {
113         int l=read();
114         int r=read();
115         query(l,r);
116     }
117     return 0;
118 }