BZOJ 2038 - 小Z的袜子

发表于 更新于 分类于 阅读次数：

题目链接：BZOJ 2038

莫队算法模板题，将原序列分成 \(\sqrt{n}\) 块，同一块内的询问按照右端点大小排序，离线询问，渐进时间复杂度 \(O(n \times \sqrt{n})\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 50000 + 5;
int n, m, c[MAX_N];
int bsz, lb[MAX_N], rb[MAX_N], blk[MAX_N], tot;
struct Query {
    int l, r, id;
    friend bool operator < (const Query &u, const Query &v) {
        if (blk[u.l] != blk[v.l]) return blk[u.l] < blk[v.l];
        else return u.r < v.r;
    }
} q[MAX_N];
LL num[MAX_N], sum;
LL ansU[MAX_N], ansD[MAX_N];
inline void add(int cid) {
    if (cid == 0) return;
    LL ori = num[cid] * (num[cid] - 1) / 2;
    ++num[cid];
    LL tar = num[cid] * (num[cid] - 1) / 2;
    sum += (tar - ori);
}
inline void remove(int cid) {
    if (cid == 0) return;
    LL ori = num[cid] * (num[cid] - 1) / 2;
    --num[cid];
    LL tar = num[cid] * (num[cid] - 1) / 2;
    sum += (tar - ori);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", c + i);
    bsz = round(sqrt(n));
    int l, r;
    for (l = 1; l <= n; l = r + 1) {
        ++tot;
        r = min(l + bsz - 1, n);
        for (int i = l; i <= r; ++i) blk[i] = tot;
        lb[tot] = l; rb[tot] = r;
    }
    /*
    for (int i = 1; i <= n; ++i) {
        printf("%d => %d-th block\n", i, blk[i]);
    }
    */
    for (int i = 1; i <= m; ++i) {
        q[i].id = i;
        scanf("%d%d", &q[i].l, &q[i].r);
    }
    sort(q + 1, q + m + 1);
    int curL = 0, curR = 0;
    for (int i = 1; i <= m; ++i) {
        // printf("sum = %d, curL = %d, curR = %d\n", sum, curL, curR);
        while (curL < q[i].l) remove(c[curL]), ++curL;
        while (curL > q[i].l) --curL, add(c[curL]);
        while (curR < q[i].r) ++curR, add(c[curR]);
        while (curR > q[i].r) remove(c[curR]), --curR;
        LL len = q[i].r - q[i].l + 1;
        LL u = len * (len - 1) / 2;
        if (u == 0 || sum == 0) {
            ansU[q[i].id] = 0;
            ansD[q[i].id] = 1;
        } else {
            LL g = __gcd(u, sum);
            ansU[q[i].id] = sum / g;
            ansD[q[i].id] = u / g;
        }
    }
    for (int i = 1; i <= m; ++i) printf("%lld/%lld\n", ansU[i], ansD[i]);
    return 0;
}