bzoj2038【2009國家集訓隊】小Z的襪子(hose)
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
【樣例解釋】
詢問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。
HINT
這道題方法是莫隊算法，一種用於處理不帶修改的區間查詢問題的離線算法。
如果我們已知[l,r]的答案，並且左(右)端點移動一個單位後的答案能在O(1)時間內求得，就可以使用莫隊算法。時間復雜度為O(n^1.5)。
對於這道題而言，我們用s[1]表示當前區間每種顏色襪子的個數，t表示當前區間襪子的總數。
則最終答案ans=∑(s[i]*(s[i]-1))/(t*(t-1))=(∑(s[i]^2-)-∑(s[i]))/(t^2-t)=(∑(s[i]^2)-t)/(t^2-t)。
這樣我們只需要維護s數組和s[i]的平方和，就可以O(1)時間內進行轉移了。
莫隊算法其實就是一種暴力算法，只是與普通暴力算法不同，它將不同的詢問進行了合理的排序，從而最小化了操作次數。
那如何排序才是最合理的呢？
我們將整個大區間分塊，分成sqrt(n)塊，每塊sqrt(n)個數。再將所有詢問排序，以左端點所在塊為第一關鍵字，以右端點為第二關鍵字。排序之後計算每個區間答案，區間端點移動就暴力計算新的答案。
以下是時間復雜度的分析：
左端點所在塊最多sqrt(n)種情況，而同一個塊內右端點最多移動n的范圍，所以右端點移動的總復雜度為O(n^1.5)。左端點每次移動范圍為O(sqrt(n))，一共移動n次，所以左端點移動復雜度也為O(n^1.5)。加起來總復雜度為O(n^1.5)。
這樣，這道題就可以完美解決了。
這裡有一個關於曼哈頓距離最小生成樹和莫隊算法的鏈接：
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 50005
using namespace std;
int n,m;
int pos[maxn],c[maxn];
ll s[maxn],sum;
struct data{int l,r,id;ll x,y;}a[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline bool cmp(data a,data b)
{
return pos[a.l]==pos[b.l]?a.ra[i].r;r--) update(r,-1);
for(;la[i].l;l--) update(l-1,1);
if (a[i].l==a[i].r)
{
a[i].x=0;a[i].y=1;
continue;
}
a[i].x=sum-(a[i].r-a[i].l+1);
a[i].y=(ll)(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
ll tmp=gcd(a[i].y,a[i].x);
a[i].x/=tmp;a[i].y/=tmp;
}
sort(a+1,a+m+1,cmpid);
F(i,1,m) printf("%lld/%lld\n",a[i].x,a[i].y);
return 0;
}
