HDU 6534 - Chika and Friendly Pairs

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

题目链接：HDU 6534

考虑莫队算法，对 \(a_i\)、\(a_i + k\)、\(a_i - k\) 进行离散化，用树状数组维护一个值域的前缀和。渐进时间复杂度 \(O(n \times \sqrt{n} \times \log n)\)。

这里要注意我们对于每一个 \(a_i\)，要先预处理出 \(a_i - k\)、\(a_i\) 和 \(a_i + k\) 离散化之后的值，然后在 add 和 remove 操作的时候就可以 \(O(1)\) 得到它们离散化之后的结果，否则会TLE。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline void getInt(int &x) {
    x = 0; char ch = getchar(); int sgn = 1;
    while (!isdigit(ch)) { if (ch == '-') sgn = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    x *= sgn;
}
const int MAX_N = 27000 + 5;
int n, m, k, a[MAX_N];
int qId[MAX_N], qIdSub[MAX_N], qIdAdd[MAX_N];
int d[MAX_N * 3], tot;
int c[MAX_N * 3];
inline int getId(const int &u) {
    return lower_bound(d + 1, d + tot + 1, u) - d;
}
inline int lowbit(const int &x) {
    return x & (-x);
}
inline void update(int pos, const int &v) {
    while (pos <= tot) {
        c[pos] += v;
        pos += lowbit(pos);
    }
}
inline int query(int pos) {
    int ret = 0;
    while (pos >= 1) {
        ret += c[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
int bsz, bt, lb[MAX_N], rb[MAX_N], blk[MAX_N];
struct Query {
    int l, r, id;
    friend inline bool operator < (const Query &u, const Query &v) {
        if (blk[u.l] == blk[v.l]) return u.r < v.r;
        else return blk[u.l] < blk[v.l];
    }
} q[MAX_N];
int ans[MAX_N];
int sum;
inline void add(const int &u) {
    if (u == 0) return;
    sum += (query(qIdAdd[u]) - query(qIdSub[u] - 1));
    update(qId[u], 1);
}
inline void remove(const int &u) {
    if (u == 0) return;
    update(qId[u], -1);
    sum -= (query(qIdAdd[u]) - query(qIdSub[u] - 1));
}
int main() {
    getInt(n), getInt(m), getInt(k);
    for (int i = 1; i <= n; ++i) getInt(a[i]);
    for (int i = 1; i <= n; ++i) {
        d[++tot] = a[i] - k;
        d[++tot] = a[i];
        d[++tot] = a[i] + k;
    }
    sort(d + 1, d + tot + 1);
    tot = unique(d + 1, d + tot + 1) - d - 1;
    for (int i = 1; i <= n; ++i) {
        qId[i] = getId(a[i]);
        qIdSub[i] = getId(a[i] - k);
        qIdAdd[i] = getId(a[i] + k);
    }
    bsz = ceil(sqrt(n));
    int bl, br;
    for (bl = 1; bl <= n; bl = br + 1) {
        ++bt;
        br = min(bl + bsz - 1, n);
        for (int i = bl; i <= br; ++i) blk[i] = bt;
    }
    for (int i = 1; i <= m; ++i) {
        q[i].id = i;
        getInt(q[i].l), getInt(q[i].r);
    }
    sort(q + 1, q + m + 1);
    a[0] = -1;
    int curL = 0, curR = 0;
    for (int i = 1; i <= m; ++i) {
        while (curL < q[i].l) remove(curL), ++curL;
        while (curL > q[i].l) --curL, add(curL);
        while (curR < q[i].r) ++curR, add(curR);
        while (curR > q[i].r) remove(curR), --curR;
        ans[q[i].id] = sum;
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}