[文章目录]
Description
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
看见出题人就瞬间知道用什么算法了，哈哈哈哈。第一道莫队。
莫队思想写到了另一道题上就不说了，每次由[L,R]计算到其他变动1的区间。
当区间变动时，将分子改变，使之始终等于可能抽到相同的袜子的方案数，分母就是总方案数，再/gcd就好啦。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,m,num[51000],c[51000],fz,fm=1;
ll gcd(ll x,ll y)
{
return (y==0) ? x:gcd(y,x%y);
}
struct node
{
ll l,r,block,fz,fm,id;
}a[50100];
bool cmp(node x,node y)
{
return x.block==y.block ? x.r < y.r : x.block<y.block;
}
bool cmp1(node x,node y)
{
return x.id<y.id;
}
void cut_L(ll &L) {fz+=2*num[c[L-1]]; num[c[L-1]]++;L--; }
void add_R(ll &R) {fz+=2*num[c[R+1]]; num[c[R+1]]++;R++; }
void add_L(ll &L) {num[c[L]]--; fz-=2*num[c[L]];L++; }
void cut_R(ll &R) {num[c[R]]--; fz-=2*num[c[R]];R--; }
int main()
{
scanf("%lld%lld",&n,&m);
ll k1=(ll)sqrt(1.0*n+0.5);
for(ll i=1;i<=n;i++) scanf("%lld",&c[i]);
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld",&a[i].l,&a[i].r);
a[i].block=(a[i].l-1)/k1+1;a[i].id=i;
}
sort(a+1,a+m+1,cmp);
ll L=1,R=0;
for(ll i=1;i<=m;i++)
{
while(R<a[i].r) add_R(R);
while(L>a[i].l) cut_L(L);
while(L<a[i].l) add_L(L);
while(R>a[i].r) cut_R(R);
fm=(R-L+1)*(R-L);
ll tmp=gcd(fz,fm);
a[i].fz=fz/tmp,a[i].fm=fm/tmp;
}
sort(a+1,a+m+1,cmp1);
for(ll i=1;i<=m;i++)
printf("%lld/%lld\n",a[i].fz,a[i].fm);
return 0;
}