BZOJ - 2038 小Z的袜子(普通莫队)

题目链接：小Z的袜子

题意：$n$只袜子，$m$个询问，每次回答有多大概率在$[L,R]$区间内抽到两只颜色相同的袜子

思路：普通莫队，如果两个询问左端点在一个块内，则按询问右端点排序，否则按照所在块的序号排序，维护一个数组$num$，表示在区间$[L,R]$中，颜色为$c$的袜子有$num[c]$只，令变量$res=\sum_{c}num[c]*(num[c]-1)/2$，显然对于每个区间$[L,R]$抽到同色袜子的概率就是$\frac{res}{C_{R-L+1}^{2}}$，每次移动区间时修改$num[c]$，同时更新$res$即可，时间复杂度$O(n^{\frac{3}{2}})$

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = ;

struct node {

    int l, r, id;

};

int n, m, a[N];

int block, belong[N], tot, l[N], r[N];

ll num[N], res, mol[N], den[N];

node q[N];

void build()

{

    block = sqrt(n);

    tot = n / block;

    if (n % block) tot++;

    for (int i = ; i <= tot; i++) {

        l[i] = (i - ) * block + ;

        r[i] = i * block;

    }

    r[tot] = n;

    for (int i = ; i <= n; i++)

        belong[i] = (i - ) / block + ;

}

bool cmp(node a, node b)

{

    if (belong[a.l] != belong[b.l])

        return belong[a.l] < belong[b.l];

    return a.r < b.r;

}

void add(int x)

{

    res = res - num[a[x]] * (num[a[x]] - ) / ;

    num[a[x]]++;

    res = res + num[a[x]] * (num[a[x]] - ) / ;

}

void sub(int x)

{

    res = res - num[a[x]] * (num[a[x]] - ) / ;

    num[a[x]]--;

    res = res + num[a[x]] * (num[a[x]] - ) / ;

}

ll c(int n)

{

    return (ll)n * (n - ) / ;

}

ll gcd(ll a, ll b)

{

    return  == b ? a : gcd(b, a % b);

}

int main()

{

    scanf("%d%d", &n, &m);

    build();

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    for (int i = ; i <= m; i++) {

        scanf("%d%d", &q[i].l, &q[i].r);

        den[i] = c(q[i].r - q[i].l + );

        q[i].id = i;

    }

    sort(q + , q + m + , cmp);

    int L = , R = ;

    for (int i = ; i <= m; i++) {

        while (q[i].l < L) add(--L);

        while (q[i].r > R) add(++R);

        while (q[i].l > L) sub(L++);

        while (q[i].r < R) sub(R--);

        mol[q[i].id] = res;

    }

    for (int i = ; i <= m; i++) {

        ll d = gcd(mol[i], den[i]);

        if ( == mol[i]) printf("0/1\n");

        else printf("%lld/%lld\n", mol[i] / d, den[i] / d);

    }

    return ;

}