国家集训队 小Z的袜子

发表于2020-07-13更新于2023-09-15字数统计775阅读时长8分

小Z的袜子

Description

多组询问求给定区间 [li,ri][l_i,r_i] 中取出相同两个数的概率。

Solution

  • 设区间内某种颜色的数目为 cntcolorcnt_{color}。
  • 则概率为 Σcntcolor(cntcolor−1)(r−l+1)(r−l)\frac{\Sigma{}cnt_{color}(cnt_{color} − 1)}{(r − l + 1)(r − l)}。
  • 将询问分块，一般取块的长度为 sqrt(n)sqrt(n) 或 nsqrt(2∗m/3)\frac{n}{sqrt(2 * m / 3)}。询问所在的块由询问左端点lil_i 决定。
    1
    2
    3
    4
    5
    read(n), read(m), Len = n / sqrt(m * 2.0 / 3);
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= m; i++) 
        read(Q[i].l), read(Q[i].r), Q[i].id = i, Q[i].block = Q[i].l / Len;
    sort(Q + 1, Q + m + 1, cmp1);
  • 排序: 询问 qiq_i，qjq_j所在块相同则按其右端点排序，否则按块的编号升序排序。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct query {
        int l, r, id, block, x/*记录询问分子*/, y/*记录询问分母*/;
    }Q[MAXN];

    inline bool cmp1 (const query &a, const query &b) {
      return (a.block== b.block) ? a.r < b.r : a.block < b.block;
    }
    inline bool cmp2 (const query &a, const query &b) { //按照原始顺序排序
        return a.id < b.id;
    }
  • 询问时，用 ll，rr 记录上一次询问的位置(初始均为 1)，不断加减扩展即可(求的是 Δ\Delta)。

Code

小Z的袜子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define int long long

constexpr int MAXN = 5e4 + 4;

using namespace std;

template <typename T> inline void read(T &x) {
    int f = 1; x = 0; 
    char ch = getchar();
    while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

int n, m, Len, l, r, ans;
int c[MAXN], cnt[MAXN];
struct query {
    int l, r, id, block, x/*记录询问分子*/, y/*记录询问分母*/;
}Q[MAXN];

inline bool cmp1 (const query &a, const query &b) {
    return (a.block== b.block) ? a.r < b.r : a.block < b.block;
}

inline bool cmp2 (const query &a, const query &b) { //按照原始顺序排序
    return a.id < b.id;
}

inline int gcd(int x, int y) {
    return !y ? x : gcd(y, x % y);
}

signed main(){
    read(n), read(m), Len = n / sqrt(m * 2.0 / 3);
    for (int i = 1; i <= n; i++) read(c[i]);
    for (int i = 1; i <= m; i++) 
        read(Q[i].l), read(Q[i].r), Q[i].id = i, Q[i].block = Q[i].l / Len;
    sort(Q + 1, Q + m + 1, cmp1);
    l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        while (r < Q[i].r) {
            r++;
            ans -= cnt[c[r]] * (cnt[c[r]] - 1);
            cnt[c[r]]++;
            ans += cnt[c[r]] * (cnt[c[r]] - 1);
        }
        while (r > Q[i].r) {
            ans -= cnt[c[r]] * (cnt[c[r]] - 1);
            cnt[c[r]]--;
            ans += cnt[c[r]] * (cnt[c[r]] - 1);
            r--;
        }
        while (l < Q[i].l) {
            ans -= cnt[c[l]] * (cnt[c[l]] - 1);
            cnt[c[l]]--;
            ans += cnt[c[l]] * (cnt[c[l]] - 1);
            l++;
        }
        while (l > Q[i].l) {
            l--;
            ans -= cnt[c[l]] * (cnt[c[l]] - 1);
            cnt[c[l]]++;
            ans += cnt[c[l]] * (cnt[c[l]] - 1);
        }
        Q[i].x = ans, Q[i].y = (Q[i].r - Q[i].l + 1) * (Q[i].r - Q[i].l);
    }
    sort(Q + 1, Q + m + 1, cmp2);
    for (int i = 1; i <= m; i++)
        if (Q[i].l == Q[i].r) puts("0/1");
        else printf("%lld/%lld\n", Q[i].x / gcd(Q[i].x, Q[i].y), Q[i].y / gcd(Q[i].x, Q[i].y));
    return 0;
}