题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=2038
题目
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。
Input
输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
Output
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
Sample Input
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
Sample Output
2/5
0/1
1/1
4/15
【样例解释】
询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据规模和约定】
30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。
解题
这题是莫队算法的提出者莫涛出的。
首先常规操作一波：
将M个区间查询按照 l 所在块的大小为第一优先级、r的大小为第二优先级排序。
然后考虑怎么由区间[L，R]的答案快速地转移到区间[L’，R’]的答案。
显然分母我们可以预处理出来：C（R-L+1，2）.
假设当前区间[L，R]的分子是sum。
设buf[i]表示颜色为i的袜子的数量。
那么，从[L，R]转移到[L，R+1]的话，第R+1个袜子所属的颜色x多了一个袜子。buf[x]++.
如果buf[x]为2，sum+=1即可。
如果buf[x]>2，需要先减去C(buf[x]-1，2）再加上C（buf[x]，2）。
其他区间转移差不多。
AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;const ll maxm=5e4+7;
const ll maxn=5e4+7;ll a[maxn]; //原数组
ll N,M;
ll block;//块的大小
struct query
{ll l,r,id,belong,len;query(){}query(ll l,ll r,ll id,ll len):l(l),r(r),id(id),len(len){belong=l/block;}bool operator<(const query &o)const{if(belong==o.belong) return r<o.r;return belong<o.belong;}
}q[maxm];ll buf[maxm];
ll ans2[maxm]; //第i个查询的分母
ll ans[maxm];//ans[i]表示第i个查询的分子ll sum;
void insert(ll x)
{++buf[x];if(buf[x]==2) sum+=1;else if(buf[x]>2) sum+=-(buf[x]-1)*(buf[x]-2)/2+(buf[x])*(buf[x]-1)/2;
}
void erase(ll x)
{--buf[x];if(buf[x]==1) sum-=1;else if(buf[x]>1) sum+=-(buf[x]+1)*(buf[x])/2+(buf[x])*(buf[x]-1)/2;
}ll gcd(ll x,ll y)
{if(x<y) swap(x,y);return y==0?x:gcd(y,x%y);
}
int main()
{while(~scanf("%lld%lld",&N,&M)){block=(ll)sqrt(N+0.5);for(ll i=1;i<=N;i++)scanf("%lld",&a[i]);for(ll i=1;i<=M;i++){ll l,r;scanf("%lld%lld",&l,&r);q[i]=query(l,r,i,r-l+1);ans2[i]=(r-l+1)*(r-l)/2;}sort(q+1,q+1+M);ll L=1,R=1;memset(buf,0,sizeof(buf));// buf.clear();sum=0;insert(a[1]);for(ll i=1;i<=M;i++){ll &tmp=ans[q[i].id];query &qi=q[i];while(R<qi.r) insert(a[++R]);while(L>qi.l) insert(a[--L]);while(R>qi.r) erase(a[R--]);while(L<qi.l) erase(a[L++]);tmp=sum;}for(ll i=1;i<=M;i++){ll ans1=ans[i];if(ans1==0) printf("0/1\n");else{printf("%lld/%lld\n",ans1/gcd(ans1,ans2[i]),ans2[i]/gcd(ans1,ans2[i]));}}}return 0;
}