「BZOJ 2038」小Z的袜子 - 莫队

给一个数列 ~ ，给出 个询问，每次询问 ~ 中，任选两个数相同的概率。

题解

先按照 分块，以区间左端点所在块为第一关键字，区间右端点为第二关键字排序，使用莫队算法。

问题可转化为：求 ~ 中相等的数字对数。

记某个时刻每个数字 的出现次数为 考虑每个数字对答案的贡献，答案为：

每加进来或删去一个数字时，可以重新计算单个数字对答案的贡献来得到新的答案。

计算出相等的对数后，除以总对数即为最终答案。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 50000;
const int MAXM = 50000;

long long gcd(const long long a, const long long b) {
    return !b ? a : gcd(b, a % b);
}

struct Fraction {
    long long a, b;

    void print() const {
        const long long g = gcd(a, b);
        printf("%lld/%lld\n", a / g, b / g);
    }
};

struct Query {
    int id, l, r;
    Fraction ans;
} Q[MAXM];

int n, m;
int a[MAXN];

bool compareByBlock(const Query &a, const Query &b) {
    static int s = floor(sqrt(m) + 1);
    if (a.l / s == b.l / s) return a.r < b.r;
    else return a.l / s < b.l / s;
}

bool compareById(const Query &a, const Query &b) {
    return a.id < b.id;
}

inline long long calc(const long long x) {
    return x * (x - 1);
}

inline void work() {
    static int cnt[MAXN];
    bool flag = false;
    long long x = 0;
    for (int i = 0, l, r; i < m; i++) {
        Query &q = Q[i];
        q.l--, q.r--;
        if (!flag) {
            l = q.l, r = q.r, flag = true;
            for (int i = l; i <= r; i++) x -= calc(cnt[a[i]]), x += calc(++cnt[a[i]]);
        } else {
            while (q.l < l) l--, x -= calc(cnt[a[l]]), x += calc(++cnt[a[l]]);
            while (q.r > r) r++, x -= calc(cnt[a[r]]), x += calc(++cnt[a[r]]);
            while (q.l > l) x -= calc(cnt[a[l]]), x += calc(--cnt[a[l]]), l++;
            while (q.r < r) x -= calc(cnt[a[r]]), x += calc(--cnt[a[r]]), r--;
        }

        q.ans.a = x, q.ans.b = calc(q.r - q.l + 1);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), a[i]--;
    for (int i = 0; i < m; i++) scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;

    std::sort(Q, Q + m, &compareByBlock);
    work();
    std::sort(Q, Q + m, &compareById);

    for (int i = 0; i < m; i++) Q[i].ans.print();

    return 0;
}