BZOJ 2038 小Z的襪子 （莫隊算法）

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 必須為最簡分數。( N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N )

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      

思路

區間任意挑選兩個的組合數很簡單，那剩下的問題便是該區間内有多少組相同的顔色。

我們知道，這樣的情況共有 ∑vi=1C2f(i) 種，其中 v 為所有的顔色數目， f(i) 為顔色 i

等價于 ∑vi=1f(i)2−f(i)2 ，即 ∑vi=1f(i)22−r−l+12

于是我們可以使用莫隊算法來解決這個問題啦~

每個區間可以抽象成平面中的點，每次轉移的花費都相當于從某一點到另一點的曼哈頓距離，是以最好的做法便是在曼哈頓最小生成樹上的轉移啦。

不過我們有一種更簡潔的方式 — 分塊

利用分塊，我們可以實作 O(nn√)

1. 排序：以左端點為第一關鍵字，右端點為第二關鍵字排序
2. 從左到右處理所有的詢問（離線）
3. 不斷調整​

   ​l,r​

   ​ 的位置并同時修改結果

AC 代碼

#include<bits/stdc++.h>
using namespace std;

const int maxn = 50010;
typedef long long LL;
int n,m,unit;
int col[maxn];
LL ans,s[maxn];

LL gcd(LL a,LL b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}

struct node
{
    int l,r,id;
    LL cnt,res;
    void reduce()
    {
        LL gc=gcd(cnt,res);
        cnt/=gc;
        res/=gc;
    }
} a[maxn];

inline void update(int x,int add)
{
    ans-=(LL)s[col[x]]*s[col[x]];
    s[col[x]]+=add;
    ans+=(LL)s[col[x]]*s[col[x]];
}

inline void init()
{
    ans=0;
    memset(s,0,sizeof(s));
}

bool cmp1(const node &x,const node &y)
{
    if(x.l/unit!=y.l/unit)      // 分塊
        return x.l/unit<y.l/unit;
    return x.r<y.r;
}

bool cmp2(const node &x,const node &y)
{
    return x.id<y.id;
}

void solve()
{
    init();
    sort(a,a+m,cmp1);
    for(int i=0,l=1,r=0; i<m; i++)
    {
        for(; r<a[i].r; r++)update(r+1,1);
        for(; r>a[i].r; r--)update(r,-1);
        for(; l<a[i].l; l++)update(l,-1);
        for(; l>a[i].l; l--)update(l-1,1);
        a[i].cnt=ans-(r-l+1);
        a[i].res=(LL)(r-l+1)*(r-l);
        a[i].reduce();
    }
    sort(a,a+m,cmp2);
    for(int i=0; i<m; i++)
        printf("%lld/%lld\n",a[i].cnt,a[i].res);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        unit=(int)sqrt(n);
        for(int i=1; i<=n; i++)
            scanf("%d",col+i);
        for(int i=0; i<m; i++)
            scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
        solve();
    }
    return 0;
}