[国家集训队]小Z的袜子（莫队）

[国家集训队]小Z的袜子一题是莫队的模板，但需要推出式子，求GCD。

在一个没有星星的晚上， q0000000 同学被一道蓝题切爆了。

这里是题目传送门和千辛万苦后的AC记录。

一、 关于思路

这天晚上， zsy 讲了莫队，他给出这道题作为练习。事实上，看到这种所谓“两只袜子颜色相同”——类似于区间众数的题目，首先就要想到 主席树 莫队。

题目要求里，“从该询问的区间 \([L,R]\) 中随机抽出两只袜子颜色相同的概率”，可以换一种说法：在静态区间 \([L,R]\) 中，总共有多少个点对？有多少个两点相同的点对？

Q： 为什么题目要求“答案以分数形式输出”？

A： 一个提示（前者是分母，后者的 \(sum\) 是分子）。

二、 关于式子

生平仅见的好推的式子，出题人太良心了。

对于问题 1 ，观察样例不难发现，区间内总共的点对数为 \(\sum_{i=1}^{r-l}\) ,等差数列求和，即为 \((r-l+1)*(r-l)/2\) 。

对于问题 2 ，相似地，每种颜色内部构成的点对数为 \(cnt_x*(cnt_x-1)/2\) 。而所有的颜色加起来，就是 \(\sum_i cnt_x*(cnt_x-1)/2\) 。

最终的结果为两式相除。

三、 关于代码

核心部分

add()

和

del()

函数，写了几遍都嫌太麻烦。最后发现，对于每一次移位，不需要考虑详细的贡献，直接一减一加就解决了。

inline void add(const int &x){
	maxx-=cnt[x]*(cnt[x]-1)/2;
	++cnt[x];
	maxx+=cnt[x]*(cnt[x]-1)/2;
}
inline void del(const int &x){
	maxx-=cnt[x]*(cnt[x]-1)/2;
	--cnt[x];
	maxx+=cnt[x]*(cnt[x]-1)/2;
}
           

边界条件虽然有，但和没有一样（有点好，就是有点坏）。

四、关于爆零

1. cmp1()

   cmp2()

   全部写挂；切记，第一次按照左端点排序，第二次分奇偶性排序！ 这个 bug 直到最后才看出来，因为它导致的是 TLE 而不是 WA ……

五、 AC 代码

//(r-l+1)*(r-l)/2
//sum of x*(x-1)/2
#include<stdio.h>
#include<math.h>
#include<algorithm>
//#pragma GCC optimize(2)
#define ri register int
const int N=50000+10;
typedef long long ll;
struct node{int l,r,id,gr;}q[N];
int n,m,a[N],cnt[N],maxx,ans[N];
ll l1[N],r1[N];
inline int rd(){
	ri x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f^=1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?x:-x;
}
inline bool cmp1(const node &a,const node &b){return a.l<b.l;}
inline bool cmp2(const node &a,const node &b){
	return a.gr==b.gr?(a.gr&1?a.r<b.r:a.r>b.r):a.gr<b.gr;
}
int gcd(const ll &a,const ll &b){return b?gcd(b,a%b):a;}
inline void add(const int &x){
	maxx-=cnt[x]*(cnt[x]-1)/2;
	++cnt[x];
	maxx+=cnt[x]*(cnt[x]-1)/2;
}
inline void del(const int &x){
	maxx-=cnt[x]*(cnt[x]-1)/2;
	--cnt[x];
	maxx+=cnt[x]*(cnt[x]-1)/2;
}
int main(){
//	freopen("in1.txt","r",stdin);
//	freopen("ans.txt","w",stdout);
	n=rd(),m=rd();
	for(ri i=1;i<=n;++i) a[i]=rd();
	for(ri i=1;i<=m;++i)
		q[i].l=l1[i]=rd(),q[i].r=r1[i]=rd(),q[i].id=i;
	std::sort(q+1,q+m+1,cmp1);	
	ri t=n/sqrt(m*2/3);
	for(ri i=1;i<=m;++i) q[i].gr=i/t+1;
	std::sort(q+1,q+m+1,cmp2);
	ri l=q[1].l,r=q[1].r;
	for(ri i=l;i<=r;++i) add(a[i]);
	ans[q[1].id]=maxx;
	for(ri i=2;i<=m;++i){
		while(l>q[i].l) add(a[--l]);
		while(r<q[i].r) add(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		ans[q[i].id]=maxx;
	}
	for(ri i=1,x;i<=m;++i){
		if(l1[i]==r1[i]) puts("0/1");
		else{
			x=gcd((ll)ans[i],(ll)(r1[i]-l1[i]+1)*(r1[i]-l1[i])/2);
			printf("%d/%lld\n",ans[i]/x,(ll)((r1[i]-l1[i]+1)*(r1[i]-l1[i])/2)/x);	
		}
	}
	return 0;
}
           

THE END