https://www.lydsy.com/JudgeOnline/problem.php?id=2038
思路：离线做法，将所有的询问先存下来，然后将区间分为sqrt(n)份，然后按照区间给询问排个序，按照询问区间左端点所在的块为第一排序顺序，询问区间右端点为第二排序标准。
之后就是通过利用两个指针在询问区间来回移动，前提是每改变一个位置可以O（1）的得到它增加或减少这个元素所对应的值，每变化一个元素就要改变它所对应的答案值。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
int color[maxn];
struct note
{
ll id,l,r,fz,fm;
} ans[maxn];
int block[maxn];
int sum[maxn];
int cmp1(note a,note b)
{
if(block[a.l]<block[b.l]) return 1;
if(block[a.l]>block[b.l]) return 0;
return a.r<b.r;
}
ll cmp2(note a,note b)
{
return a.id<b.id;
}
int gcd(ll a,ll b)
{
return a%b==0?b:gcd(b,a%b);
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=1; i<=n; i++)
scanf("%d",&color[i]);
for(int i=1; i<=q; i++)
{
scanf("%d%d",&ans[i].l,&ans[i].r);
ans[i].id=i;
}
block[0]=sqrt(n);
for(int i=1; i<=n; i++)
block[i]=(i-1)*block[0]+1;
sort(ans+1,ans+q+1,cmp1);
int last_l,last_r;
last_l=1;
last_r=0;
ll temp=0;
for(int i=1; i<=q; i++)
{
ans[i].fm=(ans[i].r-ans[i].l+1)*(ans[i].r-ans[i].l);
if(last_l<ans[i].l)
{
for(int j=last_l; j<ans[i].l; j++)
{
temp=temp-(sum[color[j]]*2-1);
sum[color[j]]--;
}
}
if(last_l>ans[i].l)
{
for(int j=last_l-1; j>=ans[i].l; j--)
{
temp=temp+(sum[color[j]]*2+1);
sum[color[j]]++;
}
}
if(last_r<ans[i].r)
{
for(int j=last_r+1; j<=ans[i].r; j++)
{
temp=temp+(sum[color[j]]*2+1);
sum[color[j]]++;
}
}
if(last_r>ans[i].r)
{
for(int j=last_r; j>ans[i].r; j--)
{
temp=temp-(sum[color[j]]*2-1);
sum[color[j]]--;
}
}
ans[i].fz=temp-(ans[i].r-ans[i].l+1);
last_l=ans[i].l;
last_r=ans[i].r;
}
sort(ans+1,ans+1+q,cmp2);
for(int i=1; i<=q; i++)
{
// printf("%lld %lld
",ans[i].fz,ans[i].fm);
if(ans[i].fz==0)
{
printf("0/1
");continue;
}
ll t=gcd(ans[i].fz,ans[i].fm);
printf("%lld/%lld
",ans[i].fz/t,ans[i].fm/t);
}
}