题意
给定一个有n个数(1<=n<=5e4)的序列C(1<=ci<=n)。有m个询问（1<=m<=5e4），每次给定一个区间[l,r]，求给区间中任取两个所在位置不同的数取到对应ci的值相等的概率，用最简整数比输出。注：不强制在线
题解
本题是莫队的模板题。那么莫队是什么呢？莫队是我们国家队队爷的莫涛提出的基于分块的毒瘤算法。具体实现方法为：对询问进行分块。先将所有询问按照l端点从小到大排序，再在每个块中按照r端点从小到大排序。对于每个块的第一个数，我们用暴力求出它的值，其余的根据原有的的范围为基础进行扩展即可。以不带修的莫队为例，我们以√n为块的大小，那么它的复杂度是O(n√n）的。本题就是裸的莫队板子。直接开一个数组维护区间内每一个ci的个数，然后排列组合一下就完事啦！
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int ret=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return w*ret;
}
int n,m;
int a[50010];
struct node{
int l,r;
int id;
}f[50010];
bool cmp1(node p,node q)
{
if(p.l!=q.l) return p.l<q.l;
else return p.r<q.r;
}
bool cmp2(node p,node q)
{
return p.r<q.r;
}
struct node2{
long long p,q;
}ans[50010];
int t;
int tot;
int lp,rp;
long long cnt=0;
long long tmp[50010];
void cal1(int l,int r)
{
cnt=0;
memset(tmp,0,sizeof(tmp));
for(int i=l;i<=r;i++)
{
int x=a[i];
cnt-=tmp[x]*(tmp[x]-1)/2;
tmp[x]++;
cnt+=tmp[x]*(tmp[x]-1)/2;
}
lp=l,rp=r;
}
void cal2(int l,int r)
{
if(lp>l)
{
for(int i=l;i<lp;i++)
{
int x=a[i];
cnt-=tmp[x]*(tmp[x]-1)/2;
tmp[x]++;
cnt+=tmp[x]*(tmp[x]-1)/2;
}
lp=l;
}
if(lp<l)
{
for(int i=lp;i<l;i++)
{
int x=a[i];
cnt-=tmp[x]*(tmp[x]-1)/2;
tmp[x]--;
cnt+=tmp[x]*(tmp[x]-1)/2;
}
lp=l;
}
if(rp<r)
{
for(int i=rp+1;i<=r;i++)
{
int x=a[i];
cnt-=tmp[x]*(tmp[x]-1)/2;
tmp[x]++;
cnt+=tmp[x]*(tmp[x]-1)/2;
rp++;
}
rp=r;
}
}
long long gcd(long long a,long long b)
{
return (b==0)? a:gcd(b,a%b);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) f[i].l=read(),f[i].r=read(),f[i].id=i;
sort(f+1,f+m+1,cmp1);
t=sqrt(n);
tot=n/t;
if(t*tot<n) tot++;
for(int i=1;i<=tot;i++)
{
int l=(i-1)*t+1,r=min(i*t,n);
sort(f+l,f+r+1,cmp2);
start:
if(f[l].l==f[l].r)
{
ans[f[l].id].p=0;
ans[f[l].id].q=1;
l++;
goto start;
}
else
{
cal1(f[l].l,f[l].r);
long long num=(long long)(f[l].r-f[l].l+1);
ans[f[l].id].p=cnt,ans[f[l].id].q=(num-1)*num/2;
}
for(int j=l+1;j<=r;j++)
{
if(f[j].l==f[j].r)
{
ans[f[j].id].p=0;
ans[f[j].id].q=1;
}
else
{
cal2(f[j].l,f[j].r);
long long num=(long long)(f[j].r-f[j].l+1);
ans[f[j].id].p=cnt,ans[f[j].id].q=(num-1)*num/2;
}
}
}
for(int i=1;i<=m;i++)
{
long long x=gcd(ans[i].p,ans[i].q);
printf("%lld/%lld\n",ans[i].p/x,ans[i].q/x);
}
return 0;
}
