莫队
莫队可以快速找到某区间的元素个数，元素最大值，最小值……
遍历莫队
举个小例子：
1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
设： l为左边界，r为右边界，sum为元素个数，shu为现有的数存的数组（假设数据很小）
求1,2区间分别出现次数最多的数的和（若一样多，以最小的数为例）。
1区间：0~6
2区间：3~8
先来求1区间出现最多次的数：
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=1,shu[1]++;(shu[1]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=2,shu[3]++;(shu[3]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=3,shu[4]++;(shu[4]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=4,shu[2]++;(shu[2]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=5,shu[3]++;(shu[3]=2)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=6,shu[4]++;(shu[4]=2)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=7,shu[2]++;(shu[2]=2)
上面可以发现，2,3,4都出现了两次，所以取2（按题意）
下面 找区域2，出现次数最多的数。出现区域2次数最多的数
2区间：3~8
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=7,shu[2]++;(shu[2]=2)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=6,shu[1]--;(shu[1]=0)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=5,shu[3]--;(shu[3]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=4,shu[4]--;(shu[4]=1)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=5,shu[3]++;(shu[3]=2)
数列： 1 3 4 2 3 4 2 3 6 7 8
下标： 0 1 2 3 4 5 6 7 8 9 10
左端点 l
右端点 r
sum=6,shu[6]++;(shu[6]=1)
由上述可以得到2,3次数一样多取2
综上，答案呼之欲出了，2+2=4。回归
因为有好几组询问，所以每回莫队都是要变得，通过上一个结果，该加的加，该减的减，再通过数学的$C^n_m$运算，就可以搞定了
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<queue>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
int n,m,pp[50005],c[50005];
long long s[50005],ans;
struct data{
int l,r,id;
long long a,b;
}a[50005];
bool cmp(const data & a,const data & b){
if(pp[a.l]==pp[b.l])
return a.r<b.r;
return a.l<b.l;
}
bool ccmp(const data & a,const data & b){
return a.id<b.id;
}
void update(int p,int add){
ans-=s[c[p]]*s[c[p]];
s[c[p]]+=add;
ans+=s[c[p]]*s[c[p]];
}
void gai(){
for(int i=1,l=1,r=0;i<=m;i++){
for(;r<a[i].r;r++)update(r+1,1);
for(;r>a[i].r;r--)update(r,-1);
for(;l<a[i].l;l++)update(l,-1);
for(;l>a[i].l;l--)update(l-1,1);
if(a[i].l==a[i].r){
a[i].a=0;
a[i].b=1;
continue;
}
a[i].a=ans-(a[i].r-a[i].l+1);
a[i].b=(a[i].r-a[i].l+1)*1ll*(a[i].r-a[i].l);
long long g=__gcd(a[i].a,a[i].b);
a[i].a/=g;
a[i].b/=g;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
int b_b=sqrt(n);
for(int i=1;i<=n;i++)pp[i]=(i-1)/b_b+1;
for(int i=1;i<=m;i++){
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
gai();
sort(a+1,a+m+1,ccmp);
for(int i=1;i<=m;i++)
printf("%lld/%lld\n",a[i].a,a[i].b);
return 0;
}
