小Z的妹子袜子这道题用的是莫队算法，据说解决离线区间询问几乎无敌。
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。
包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）
对于一个区间l，r，如果其中有v种颜色，$f[v_i]$表示第i种颜色，有多少个袜子。那么l，r的概率就是：
$LARGEfrac{sum_{i=1}^{v}C_2^{f_i}}{C_2^{r-l+1}}=frac{sum_{i=1}^vf_i^2-sum_{i=1}^{v}f_i}{C_2^{r-l+1}}=frac{sum_{i=1}^{v}f_i^2-(r-l+1)}{2C_2^{r-l+1}}$
，我们发现，除了$sum_{i=1}^{v}f_i^2$，其它都可以方便求出。那么怎么求这个各个颜色的袜子数目的平方和呢？
对于区间l，r，如果询问是l，r+1，我们发现$S_现=S_原-f_x^2+(f_x+1)^2=S_原+2f_x+1$。我们只需加上$2f_x+1$即可。这启发我们遇到一个新询问区间，都可以通过一个个加过来解决。只需维护l，r两个指针即可。
但是，对于随机数据，这样的做法显然是$n^2$的。于是就有一个神奇的莫队算法：把所有查询都根据左端点的pos分块，然后排序。如果左端点位于同一个块，就按照右端点排序，然后l，r再移动，复杂度就变成了$nsqrt{n}$。。
为什么呢？因为左端点在一个块时，右端点最多移动$sqrt{n}$次，而左端点最多跳$sqrt{n}*sqrt{n}$次，而有$sqrt{n}$个这样的块，这样左端点时间复杂度比右端点大，所以在一个块中的时间复杂度是n，乘上有$sqrt{n}$个块，就是$O(nsqrt{n})$。而一共有$sqrt{n}$次左端点跨越块，右端点每次这样移动n，左端点每次移动$sqrt{n}$，也就是说右端点时间复杂度更大，同样时间复杂度也是$O(nsqrt{n})$。
1 #include <cmath> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 typedef long long LL; 7 const int maxn=5e4+5; 8 int n, m, l=1, r, ans; 9 int color[maxn], f[maxn]; 10 11 LL gcd(LL x, LL y){ return y?gcd(y, x%y):x; } 12 13 struct query{ 14 int l, r, pos; 15 //又双叒叕忘记LL了 16 int id; LL ans; 17 }q[maxn]; 18 19 bool cmp_md(query a, query b){ 20 return a.pos!=b.pos?a.pos<b.pos:a.r<b.r; } 21 bool cmp_id(query a, query b){ 22 return a.id<b.id; } 23 24 void modify(int now, int shift){ 25 //别忘记+1! 26 ans+=2*shift*f[color[now]]+1; 27 f[color[now]]+=shift; 28 } 29 30 int main(){ 31 scanf("%d%d", &n, &m); 32 for (int i=1; i<=n; ++i) scanf("%d", &color[i]); 33 int sqrtn=sqrt(double(n)); 34 for (int i=0; i<m; ++i){ 35 scanf("%d%d", &q[i].l, &q[i].r); 36 q[i].pos=q[i].l/sqrtn; q[i].id=i; 37 } 38 sort(q, q+m, cmp_md); 39 for (int i=0; i<m; ++i){ 40 //这里要是反过来的! 41 //注意拓展和删除的区别.. 42 if (q[i].l<l) for (; l!=q[i].l; --l) modify(l-1, 1); 43 if (q[i].l>l) for (; l!=q[i].l; ++l) modify(l, -1); 44 if (q[i].r>r) for (; r!=q[i].r; ++r) modify(r+1, 1); 45 if (q[i].r<r) for (; r!=q[i].r; --r) modify(r, -1); 46 q[i].ans=ans; 47 } 48 sort(q, q+m, cmp_id); 49 LL x, y; 50 for (int i=0; i<m; ++i){ 51 x=q[i].ans-(q[i].r-q[i].l+1); 52 LL t=q[i].r-q[i].l+1; 53 y=t*(t-1); 54 int g=gcd(x, y); 55 x/=g, y/=g; 56 printf("%lld/%lld ", x, y); 57 } 58 return 0; 59 }