【分塊·莫隊】小Z的襪子
Time Limit:10000MS Memory Limit:524288K Case Time Limit:1000MS
Description
作為一個生活散漫的人，小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 Hint
【樣例解釋】 詢問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≤N，Ci≤N
使用莫隊算法的前提，在知道[l,r]的答案情況下，可以O(1)轉移至[l,r+1],[l-1,r]等等。 此題比較顯然，對式子進行一些化簡即可得出O(1)的轉移方法 
#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cstdlib>#include<queue>#include<vector>#include<cmath>#define ll long longusing namespace std;template <typename T>inline void _read(T& x){ char ch=getchar();bool sign=true; while(!isdigit(ch)){if(ch=='-')sign=false;ch=getchar();} for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0'; if(!sign)x=-x;}int base;int n,m,tot;int color[50005];int belong[50005];ll gcd(ll a,ll b){ if(b==0)return a; else return gcd(b,a%b);}struct node{ int l,r,id; ll a,b; node(){} node(int x,int y){l=x;r=y;} void simplify(){ ll t=gcd(a,b); a/=t;b/=t; }};node work[50005];bool cmp(node G,node H){ if(G.l/base==H.l/base)return G.r<H.r; else return G.l/base<H.l/base; }bool cmp2(node G,node H){ return G.id<H.id;}int cnt[50005];int main(){ int i,j,k; cin>>n>>m; for(i=1;i<=n;i++){ _read(color[i]); } base=floor(sqrt(n)+0.5); for(i=1;i<=m;i++){ _read(work[i].l); _read(work[i].r); work[i].id=i; } sort(work+1,work+1+m,cmp); //work int head,rear; head=1; rear=0; ll temp=0; for(i=1;i<=m;i++){ while(rear<work[i].r){ rear++; temp-=1ll*cnt[color[rear]]*cnt[color[rear]]; cnt[color[rear]]++; temp+=1ll*cnt[color[rear]]*cnt[color[rear]]; } while(rear>work[i].r){ temp-=1ll*cnt[color[rear]]*cnt[color[rear]]; cnt[color[rear]]--; temp+=1ll*cnt[color[rear]]*cnt[color[rear]]; rear--; } while(head<work[i].l){ temp-=1ll*cnt[color[head]]*cnt[color[head]]; cnt[color[head]]--; temp+=1ll*cnt[color[head]]*cnt[color[head]]; head++; } while(head>work[i].l){ head--; temp-=1ll*cnt[color[head]]*cnt[color[head]]; cnt[color[head]]++; temp+=1ll*cnt[color[head]]*cnt[color[head]]; } work[i].b=temp-(work[i].r-work[i].l+1); work[i].a=1ll*(work[i].r-work[i].l+1)*(work[i].r-work[i].l); work[i].simplify(); } sort(work+1,work+1+m,cmp2); for(i=1;i<=m;i++){
