[GZOI2017] 配对统计

形式化题目

给定 $n$ 个互异的整数 $a_1 \dots a_n$ 。有序对 $(x,y)$ 是好配对当 $a_y$ 是 $a_x$ 的全局最近值——即不存在 $i \neq x$ 使 $|a_x-a_i| < |a_x-a_y|$ 。 $m$ 次询问区间 $[l,r]$ 内包含多少好配对，按询问编号 $i$ 加权求和 $\sum \text{Ans}_i \times i$ 。

思路

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-10 14:12
 * update_at: 2026-08-10 14:12
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300;
const int MAXM = 300;

int n, m;
long long a[MAXN + 1];
int query_left[MAXM + 1];
int query_right[MAXM + 1];

// a[y] 是否是 a[x] 的全局最近值：不存在 i != x 使 |a[x]-a[i]| < |a[x]-a[y]|。
bool is_good_pair(int x, int y) {
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        if (llabs(a[x] - a[i]) < llabs(a[x] - a[y])) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> query_left[i] >> query_right[i];
    }

    long long answer = 0;
    for (int q = 1; q <= m; q++) {
        int left = query_left[q];
        int right = query_right[q];
        int count = 0;
        // 枚举区间内所有有序对 (x,y)，x != y
        for (int x = left; x <= right; x++) {
            for (int y = left; y <= right; y++) {
                if (x == y) continue;
                if (is_good_pair(x, y)) count++;
            }
        }
        answer += (long long)count * q;
    }

    cout << answer << '\n';
    return 0;
}

暴力对每个询问枚举区间内所有有序对，用定义逐项判断 $O(n)$ 次比较。总复杂度 $O(m n^3)$ ，仅适合 $n \le 300$ 的小数据。

好配对真的可能有 $n^2$ 个吗？

直觉上每个 $x$ 都需要遍历所有 $y$ 找最近值，但数值全部互异——如果按值从小到大排成一条线，会暴露什么？

按值排序后得到下标序列 $p_1, p_2, \dots, p_n$ ，其中 $a_{p_1} < a_{p_2} < \dots < a_{p_n}$ 。对于位置 $p_k$ ，离 $a_{p_k}$ 最近的值只能是前驱 $p_{k-1}$ 或后继 $p_{k+1}$ ，绝不可能是排序上不相邻的位置。

证明：选取任意非相邻的 $i$ （设它在排序中位于 $p_k$ 右侧且不是 $p_{k+1}$ ）。从 $a_{p_k}$ 沿值轴向右走到 $a_i$ ，必然先经过 $a_{p_{k+1}}$ 。因为排序是严格递增的， $|a_{p_k} - a_{p_{k+1}}| < |a_{p_k} - a_i|$ ，所以 $a_{p_{k+1}}$ 比 $a_i$ 更近。左侧同理——非邻居被邻居"夹逼"了。

因此每个位置至多和它的前驱、后继组成好配对。距离相等时两侧都算，总好配对数 $\le 2n$ ，而不是 $O(n^2)$ 。把平方级的问题退化成了线性级。

好配对很少了，现在怎么回答区间询问？

把每个好配对 $(x,y)$ 写成一个二维点 $(\max(x,y),\; \min(x,y))$ 。这张图展示有序对到点的映射规则（用样例 $a=[10,30,20,40]$ ，好配对共 6 个）：

text

1
2
3
4
5
6
7
8
9好配对（有序对）          二维点 (first, second)
(x, y)                   (max(x,y), min(x,y))

(1,3)        ──────►     (3,1)
(3,1)        ──────►     (3,1)    ← 方向不同的两个有序对
(3,2)        ──────►     (3,2)    映射到同一个点，不去重
(2,3)        ──────►     (3,2)
(2,4)        ──────►     (4,2)
(4,2)        ──────►     (4,2)

first 取两个下标里较大的那个，second 取较小的那个。(1,3) 和 (3,1) 是两个不同的好配对，但映射到同一个点 (3,1)——所以点可以重复，不能去重。

这张图把这些点画在 first × second 坐标系里：

text

1
2
3
4
5
6
7
8
9
10
11second = min(x,y)
   ^
   |
2  |                        (4,2)×2
1  |           (3,1)×2   (3,2)×2
   +----+----+----+----+----+----> first = max(x,y)
   0    1    2    3    4    5

   first:       3     3     4
   second:      1     2     2
   点数量:      ×2    ×2    ×2

询问 $[l,r]$ 到底在检查什么？

对一个好配对 $(x,y)$ 来说，只要把两个下标按大小重新记成

text

1
2u = min(x,y)
v = max(x,y)

那么“ $(x,y)$ 都在 $[l,r]$ 内”就等价于

text

1l <= u <= v <= r

也就是：较小的那个下标不小于 $l$ ，较大的那个下标不大于 $r$ 。

所以把 $(x,y)$ 变成点 (first, second) 后，询问 $[l,r]$ 不是在问一个普通区间，而是在问两个方向的限制：

text

1
2
3
4
5
6
7询问 [2,3]：要求 second >= 2 且 first <= 3

点 (first, second)   是否满足 [2,3]        原因
---------------------------------------------------------
(3,1)               否                    second=1 < 2
(3,2)               是                    2 >= 2 且 3 <= 3
(4,2)               否                    first=4 > 3

这就是二维偏序：每个点有两个坐标，查询同时卡住两维——第一维 first <= r，第二维 second >= l。样例中 (3,2) 有两个重复点，所以询问 $[2,3]$ 的答案是 2。

为什么要离线处理询问？

每个询问要数满足 first ≤ r 且 second ≥ l 的点。如果按输入顺序处理询问， $r$ 忽大忽小，满足 first ≤ r 的点集会反复变化，不好维护。

把询问按 $r$ 从小到大排序后，点集只会单调增加：当扫描到某个 $r$ ，把所有 first ≤ r 的点加入桶 / Fenwick。这样第一维条件 first ≤ r 被扫描顺序自动解决，数据结构只需要维护第二维 second ≥ l。

桶维护：按 second 分桶计数

现在模型建好了，怎么高效回答每个询问？最直接的想法：按 $r$ 递增扫描，用一个桶数组记录 second 维度的分布。

将所有点按 first 排序，所有询问按 $r$ 排序。维护 bucket[1..n] 计数数组——bucket[s] 表示"已加入点中 second 恰好等于 s 的个数"：

text

1
2桶:   second=1   second=2   second=3   ...  second=n
计数:    2          2          0              0

加入点 (3,2) → bucket[2]++
回答询问 $[l,r]$ ：已加入点全都满足 first ≤ r，只需要数 second ≥ l 的——即 bucket[l] + bucket[l+1] + ... + bucket[n]

桶直观看懂了，但每次询问要 O(n) 扫一遍桶求和，m 次询问就是 O(nm)，不可接受。

Fenwick 加速桶：把 O(n) 区间求和压到 O(log n)

Fenwick 树就是"分层的桶"——每个节点管一段桶区间，单点加和前缀和都是 O(log n)。把 bucket 数组换成 Fenwick：

加入点 → BIT.add(second, 1)（和 bucket[second]++ 一个意思）
查询 second ≥ l → 已加入总数 − BIT.prefix(l-1)（比扫桶快得多）

这张图展示按 $r$ 递增扫描、Fenwick 累积 second 维度的过程：

text

1
2
3
4
5
6
7
8
9
10
11
12
13扫描 r = 1 → 2 → 3 → 4，把 first == r 的点加入 BIT

r=1,2:  没有点加入

r=3:    加入 (3,1)(3,1)(3,2)(3,2)
        已加入 = 4
        回答询问 [2,3]：
          答案 = 4 − BIT.prefix(1) = 4−2 = 2  ✓

r=4:    加入 (4,2)(4,2)
        已加入 = 6
        回答询问 [2,4]：
          答案 = 6 − BIT.prefix(1) = 6−2 = 4  ✓

桶思想为骨——每个 second 值就是一个计数桶；Fenwick 树只是给这组桶加了 O(log n) 的前缀和，不改变"按维度分桶"的本质。

有序对 $(x,y)$ 和 $(y,x)$ 是两个方向——当两者互为最近值时，两个方向都是好配对，产生两个二维点，不能去重。这样正反方向都会被 BIT 正确统计。

Python 知识

sorted(range(n), key=values.__getitem__) 得到按值排列的原下标。
key=lambda query: query[1] 明确按右端点离线排序。
重复二维点不能去重，因为相反方向是两组有序配对。

代码

cpp

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-10 14:12
 * update_at: 2026-08-10 14:12
 */
#include <bits/stdc++.h>
using namespace std;

// 单点加、前缀和、区间和。下标必须从 1 开始。
// 模板来自 rbook fenwick。
template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    static int lowbit(int x) { return x & -x; }

    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }

    T range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }
};

const int MAXN = 300005;
const int MAXM = 300005;

struct Point {
    int first;
    int second;
};

struct Query {
    int left;
    int right;
    int identity;
};

int n, m;
long long a[MAXN];       // 原数组
int ordered[MAXN];       // 按值从小到大排列的原下标
Point points[2 * MAXN];  // 好配对转成的点 (max(x,y), min(x,y))
int point_cnt;
Query queries[MAXM];

// 按值排序原下标
bool cmp_value(int x, int y) {
    return a[x] < a[y];
}

bool cmp_point(const Point &p, const Point &q) {
    if (p.first != q.first) return p.first < q.first;
    return p.second < q.second;
}

bool cmp_query(const Query &p, const Query &q) {
    if (p.right != q.right) return p.right < q.right;
    return p.left < q.left;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> queries[i].left >> queries[i].right;
        queries[i].identity = i;
    }

    // 找每个位置的值最近邻居：按值排序后，最近值只可能是前驱或后继。
    for (int i = 1; i <= n; i++) ordered[i] = i;
    sort(ordered + 1, ordered + n + 1, cmp_value);

    for (int pos = 1; pos <= n; pos++) {
        int index = ordered[pos];
        long long left_gap = LLONG_MAX;
        long long right_gap = LLONG_MAX;
        if (pos > 1) left_gap = a[index] - a[ordered[pos - 1]];
        if (pos < n) right_gap = a[ordered[pos + 1]] - a[index];

        // 前驱距离更近（或相等）：与前驱组成好配对
        if (pos > 1 && left_gap <= right_gap) {
            int other = ordered[pos - 1];
            point_cnt++;
            points[point_cnt].first = max(index, other);
            points[point_cnt].second = min(index, other);
        }
        // 后继距离更近（或相等）：与后继组成好配对
        if (pos < n && right_gap <= left_gap) {
            int other = ordered[pos + 1];
            point_cnt++;
            points[point_cnt].first = max(index, other);
            points[point_cnt].second = min(index, other);
        }
    }

    // 重复的二维点不能去重：两个相反方向是两组有序配对。
    sort(points + 1, points + point_cnt + 1, cmp_point);
    sort(queries + 1, queries + m + 1, cmp_query);

    Fenwick<int> bit(n); // 标记第二坐标（min）已加入的点
    int pointer = 0;     // 已加入的点数
    long long answer = 0;

    for (int i = 1; i <= m; i++) {
        // 右端点递增：加入所有第一坐标 <= r 的点
        while (pointer < point_cnt && points[pointer + 1].first <= queries[i].right) {
            pointer++;
            bit.add(points[pointer].second, 1);
        }
        // 总数去掉第二坐标 < l 的部分，就是两个坐标都在 [l,r] 内的配对
        long long count = pointer - bit.prefix_sum(queries[i].left - 1);
        answer += count * queries[i].identity;
    }

    cout << answer << '\n';
    return 0;
}

python

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
48import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, query_count = next(data), next(data)
values = [next(data) for _ in range(n)]
ordered = sorted(range(n), key=values.__getitem__)
pairs = []

for position, index in enumerate(ordered):
    left_gap = values[index] - values[ordered[position - 1]] if position else 10**30
    right_gap = values[ordered[position + 1]] - values[index] if position + 1 < n else 10**30
    if left_gap <= right_gap:
        other = ordered[position - 1]
        pairs.append((max(index, other), min(index, other)))
    if right_gap <= left_gap:
        other = ordered[position + 1]
        pairs.append((max(index, other), min(index, other)))

queries = sorted(((next(data) - 1, next(data) - 1, identity + 1)
                  for identity in range(query_count)), key=lambda query: query[1])
pairs.sort()
tree = [0] * (n + 1)


def add(index):
    index += 1
    while index <= n:
        tree[index] += 1
        index += index & -index


def prefix(end):
    result = 0
    while end:
        result += tree[end]
        end -= end & -end
    return result


pointer = 0
answer = 0
for left, right, identity in queries:
    while pointer < len(pairs) and pairs[pointer][0] <= right:
        add(pairs[pointer][1])
        pointer += 1
    answer += (pointer - prefix(left)) * identity
print(answer)

复杂度

排序 $O((n+m)\log n)$ ，Fenwick 操作 $O((n+m)\log n)$ ，空间 $O(n+m)$ 。

总结

先证明好配对只产生在值排序后的相邻位置之间——把 $O(n^2)$ 的候选数压到 $O(n)$ ；再把"两个下标都在区间内"转成二维偏序，用离线 Fenwick 扫描回答。两个步骤缺一不可。

数据编号	$n$	$m$	$a_i$
$1$	$\le300$	$\le300$	$1\le a_i\le 10^9$
$2$	^	^	^
$3$	$\le5000$	$\le5000$	^
$4$	^	^	^
$5$	$\le5 \times 10^4$	$\le5 \times 10^4$	^
$6$	^	^	^
$7$	^	^	^
$8$	$\le3 \times 10^5$	$\le3 \times 10^5$	^
$9$	^	^	^
$10$	^	^	^