题目描述

blablabla

样例

blablabla

(莫队) $O(N * \sqrt{N})$

分块算法的另一种重要形式：对询问分块（离线）
对所有询问对 L 升序排列，在块内按 R 升序排列
对于每块中的第一个询问（R最小的那个询问）
for循环L-R，统计每种颜色袜子的个数 cnt[color], 显然对于每个询问答案为$\sum_c\frac{num[c]*(num[c]-1)}{2}$,
循环完再求答案必定超时。所以在循环记录cnt[]数量时就要更新答案，
对于每种颜色对答案共享为 $\frac{cnt[c] * (cnt[c] - 1)}{2}$,
循环中 cnt[c] 增加（减少了）a个，则贡献变为 $\frac{(cnt[c] + a) * (cnt[c] - 1 + a)}{2}$,
相比原来增加 $a * cnt[n] + \frac{a * (a - 1)}{2}$, 就可以在更新cnt时更新答案，
在块内的询问比较和块内上一个询问的区间差，去更新cnt和答案即可

对于每个询问的答案最后都要是$\frac{ans}{C^2_{r - l + 1}}$, 毕竟求的概率

时间复杂度

参考文献

C++ 代码

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

const int N = 50005;

struct node { int l, r, id, p, f; } q[N];

int t, len, n, m, a[N], b[N], d[N], c[N] = {1};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        cin >> q[i].l >> q[i].r; q[i].id = i;
        q[i].p = (q[i].r - q[i].l + 1ll) * (q[i].r - q[i].l) >> 1;
    }
    len = sqrt(n); t = (n - 1) / len + 1;
    sort(q + 1, q + 1 + m, [](node& a, node& b) { return a.l < b.l; });
    for (int i = b[1] = d[1] = 1; i <= t && b[i] <= m; ++i, d[i] = b[i] = d[i - 1] + 1) {
        while (d[i] < m && q[d[i] + 1].l <= i * len) ++d[i];
        sort(q + b[i], q + d[i] + 1, [](node& a, node& b) { return a.r < b.r; });
    }
    for (int i = 1, l = 0, r = 0, cur = 0; d[i - 1] < m; ++i) for (int j = b[i]; j <= d[i]; ++j) {
        while (r < q[j].r) { cur += c[a[++r]]; ++c[a[r]]; }
        while (l > q[j].l) { cur += c[a[--l]]; ++c[a[l]]; }
        while (r > q[j].r) { --c[a[r]]; cur -= c[a[r--]]; }
        while (l < q[j].l) { --c[a[l]]; cur -= c[a[l++]]; }
        if (!cur) q[j].p = 1;
        else { q[j].f = __gcd(q[j].p, cur); q[j].p /= q[j].f, q[j].f = cur / q[j].f; }
    }
    sort(q + 1, q + 1 + m, [](node& a, node& b) { return a.id < b.id; });
    for (int i = 1; i <= m; ++i) cout << q[i].f << '/' << q[i].p << '\n';
    return 0;
}