Description
作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L
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。
莫队算法基础题
莫队算法是一种优化的思想
给很多组询问，每次询问一个区间的答案
我们要用一个神奇的数据结构，维护区间信息，可以由（l，r）推出（l+1，r）和（l，r+1）和（l-1，r）和（l，r-1）
这时我们把询问看成点（l，r），两个询问的转移的代价就是曼哈顿距离
然后我们求出曼哈顿最小生成树，再dfs一遍就行了，但是这样很麻烦，所以就有了一个替代品，很容易写
具体操作是先分块，分成根号n块，对询问的区间排序，第一关键字是l所在的块的编号，第二关键字是r
然后就是暴力了，用那个神奇的数据结构从上一次的询问推到这一次的询问
可以证明，这样复杂度是O（n^1.5*那个神奇的数据结构操作一次的时间）
1.对于l，因为我们按块排序，所以每一次变化不超过n^0.5，一共n次，所以是n^1.5
2.对于r，有两种情况
1>l在同一个块，因为第二关键字是r，所以这时r递增，一个块最多O（n），有n^0.5个块，所以是O（n^1.5）
2>l跨块，r最多变化n，最多有n^0.5次跨块，所以为O(n^1.5)
1 const 2 maxn=50010; 3 var 4 ll,rr,a,c,s,kuai:array[0..maxn]of longint; 5 ans:array[0..maxn,0..1]of int64; 6 n,m,w:longint; 7 8 procedure swap(var x,y:longint); 9 var 10 t:longint; 11 begin 12 t:=x;x:=y;y:=t; 13 end; 14 15 procedure sort(l,r:longint); 16 var 17 i,j,y,z:longint; 18 begin 19 i:=l; 20 j:=r; 21 y:=kuai[ll[(l+r)>>1]]; 22 z:=rr[(l+r)>>1]; 23 repeat 24 while (kuai[ll[i]]<y)or((kuai[ll[i]]=y)and(rr[i]<z)) do 25 inc(i); 26 while (kuai[ll[j]]>y)or((kuai[ll[j]]=y)and(rr[j]>z)) do 27 dec(j); 28 if i<=j then 29 begin 30 swap(ll[i],ll[j]); 31 swap(rr[i],rr[j]); 32 swap(a[i],a[j]); 33 inc(i); 34 dec(j); 35 end; 36 until i>j; 37 if i<r then sort(i,r); 38 if j>l then sort(l,j); 39 end; 40 41 procedure init; 42 var 43 i:longint; 44 begin 45 read(n,m); 46 w:=trunc(sqrt(n)); 47 for i:=1 to n do 48 kuai[i]:=i div w; 49 for i:=1 to n do 50 read(c[i]); 51 for i:=1 to m do 52 read(ll[i],rr[i]); 53 for i:=1 to m do 54 a[i]:=i; 55 sort(1,m); 56 end; 57 58 function f(x:int64):int64; 59 begin 60 exit((x*(x-1))>>1); 61 end; 62 63 function gcd(a,b:int64):int64; 64 begin 65 if b=0 then exit(a); 66 exit(gcd(b,a mod b)); 67 end; 68 69 procedure insert(x:longint;a,b:int64); 70 var 71 t:longint; 72 begin 73 if a=0 then 74 begin 75 ans[x,0]:=0; 76 ans[x,1]:=1; 77 end; 78 t:=gcd(a,b); 79 a:=a div t; 80 b:=b div t; 81 ans[x,0]:=a; 82 ans[x,1]:=b; 83 end; 84 85 procedure work; 86 var 87 lastl,lastr,i,j:longint; 88 sum:int64; 89 begin 90 lastl:=1; 91 lastr:=0; 92 sum:=0; 93 for i:=1 to m do 94 begin 95 for j:=lastr+1 to rr[i] do 96 begin 97 inc(s[c[j]]); 98 sum:=sum+f(s[c[j]])-f(s[c[j]]-1); 99 end; 100 for j:=ll[i] to lastl-1 do 101 begin 102 inc(s[c[j]]); 103 sum:=sum+f(s[c[j]])-f(s[c[j]]-1); 104 end; 105 for j:=rr[i]+1 to lastr do 106 begin 107 dec(s[c[j]]); 108 sum:=sum+f(s[c[j]])-f(s[c[j]]+1); 109 end; 110 for j:=lastl to ll[i]-1 do 111 begin 112 dec(s[c[j]]); 113 sum:=sum+f(s[c[j]])-f(s[c[j]]+1); 114 end; 115 lastl:=ll[i]; 116 lastr:=rr[i]; 117 insert(a[i],sum,f(rr[i]-ll[i]+1)); 118 end; 119 for i:=1 to m do 120 writeln(ans[i,0],'/',ans[i,1]); 121 end; 122 123 begin 124 init; 125 work; 126 end.