鸟哥（faebdc）自从虐暴NOIP2013以来依然勤奋学习，每天上各种OJ刷题，各种比赛更是不在话下。但这天他遇到了一点小小的麻烦……在一届“Orz鸟哥杯”上，题目是在是太多了！足有n道！鸟哥看得头晕眼花，他需要你的帮助。
每道题都有一个难度值ai，由于wangxz神犇已经提前帮助鸟哥将这些难度值升序排列，所以鸟哥并不想知道哪些题难度低或者高，他只想知道在某些题目ai，ai+1，…，aj中，出现最多的难度值出现的次数（他为啥想知道这么奇葩的东西呢……自己去问）。
你的任务就是对于鸟哥的每一次询问（i，j），告诉他在从ai到aj这j-i+1道题之中，出现最多的难度值出现的次数（询问共有q次）。
如果你成功地帮助了鸟哥，鸟哥将会带你通过省选。
给出一个升序排列的整数数组a1,a2,…an，你的任务是对于鸟哥的一系列询问（i，j），回答ai,ai+1,…aj中出现次数最多的值所出现的次数。
输入仅包含一组数据。
第一行为两个整数n,q（1<=n<=100000,1<=q<=200000）。第二行包含n个升序排列的整数a1,a2,…,an(-100000<=ai<=100000)，代表每一道题的难度值。以下q行每行包含两个整数i和j(1<=i<=j<=n)，代表鸟哥询问的区间。
对于每次询问，单独输出一行，该行仅有一个整数，表示该区间内出现最多的数值所出现的次数。
9 1
1 1 1 2 2 3 3 4 4
3 8
2
各个测试点1s
思路：
莫队，求众数出现的次数，cnt[]存次数，sum存的是出现次数为某个值得输的个数，如果此时得sum[]为零，则说明把此数删去，没有其他数的众数为此时的答案，答案必须减一，但减一后的sum不用加，因为之前在加到最大值之前加过一次，从之前更新过来的时候，已经加过了。
代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define N 2000000
using namespace std;
int a[N],b[N],len,n,m,tot[N];
int sum[N],cnt[N],ans,Ans[N];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
void add(int x)
{
cnt[x]++;
sum[cnt[x]]++;
ans=max(ans,cnt[x]);
}
void del(int x)
{
sum[cnt[x]]--;
if(!sum[cnt[x]])
if(ans==cnt[x])
{
ans--;
}
cnt[x]--;
}
struct node{
int l,r,pos,id;
bool operator < (const node &a)const
{
if(pos==a.pos)return r<a.r;
return pos<a.pos;
}
}e[N];
int main()
{
scanf("%d%d",&n,&m);
len=sqrt(n);
for(int i=1;i<=n;i++)a[i]=b[i]=read();
sort(b+1,b+n+1);
int le=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+le+1,a[i])-b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].l,&e[i].r);
e[i].id=i;
e[i].pos=(e[i].l-1)/len+1;
}
int l=1,r=0;
sort(e+1,e+m+1);
for(int i=1;i<=m;i++)
{
while(l<e[i].l)del(a[l++]);
while(r>e[i].r)del(a[r--]);
while(l>e[i].l)add(a[--l]);
while(r<e[i].r)add(a[++r]);
Ans[e[i].id]=ans;
}
for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
return 0;
}
原文：https://www.cnblogs.com/yelir/p/11574286.html