配对问题

配对问题就是固定右端点 `j`，把所有合法左端点 `i < j` 按条件快速数出来。

  • 枚举
  • 配对
  • 哈希表
  • 滑动窗口
  • 单调队列

一句话算法

配对问题就是固定右端点 j，把所有合法左端点 i < j 按条件快速数出来。

问题模型

给定一个序列，统计满足某种条件的下标对：

(i,j),i<j (i,j),\quad i<j

最直接的做法是两层循环枚举所有对，复杂度 O(n2)O(n^2)。

配对问题的优化思路是：

  1. 从左到右枚举右端点 j。
  2. 把 j 左边的信息维护在桶、哈希表、窗口或队列里。
  3. 对每个 j，直接查出有多少个 i 能和它配对。

通用形式：

answer=∑j=1ns(j) \text{answer}=\sum_{j=1}^{n} s(j)

其中 s(j) 表示“以 j 为右端点的合法配对数量”。

核心直觉

任意一对 (i,j) 都有唯一的右端点 j。所以按右端点分类，一定不重不漏。

黑白气球例子：

位置: 1 2 3 4 5 6
颜色: 0 1 1 0 0 1

当枚举到一个黑气球时，它能和左边所有白气球配对；当枚举到一个白气球时，它能和左边所有黑气球配对。

所以只需要维护左边有多少个 0 和多少个 1。

算法步骤

基础模板：

  1. 初始化一个维护历史信息的数据结构 state。
  2. 从左到右枚举当前位置 j。
  3. 先用 state 计算 s(j)，把它加入答案。
  4. 再把 a[j] 加入 state，供后面的右端点使用。

“查询要在插入当前元素之前”

如果先插入当前元素，就可能把 j 自己当成左端点，破坏 i < j。

算法证明

关键不变量： 处理位置 j 前，state 中只包含下标 < j 的元素信息。

  1. 初始化时，state 为空，确实没有任何左端点。
  2. 处理 j 时，先查询 state，得到的都是 i < j 的配对。
  3. 查询后才插入 a[j]，所以 a[j] 只会参与后续右端点的配对。
  4. 任意合法配对 (i,j) 会且只会在枚举到右端点 j 时被统计一次。

所以按右端点统计既不会重复，也不会遗漏。

复杂度分析

不同模型取决于 state 的维护方式：

  • 二值桶：O(n)O(n)。
  • 哈希表计数：期望 O(n)O(n)。
  • 余数桶：O(n+k)O(n + k)。
  • 滑动窗口计数：期望 O(n)O(n)。
  • 单调队列维护窗口最值：O(n)O(n)。

空间复杂度通常是桶或哈希表大小。

代码实现

二值属性不同配对

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

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

// Count pairs (i, j), i < j, with different binary values.

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

    int n;
    cin >> n;

    long long cnt[2] = {0, 0};
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ans += cnt[x ^ 1];
        ++cnt[x];
    }

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

Two Sum 配对计数

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

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

// Count pairs (i, j), i < j, with a[i] + a[j] == target.

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

    int n;
    long long target;
    cin >> n >> target;

    unordered_map<long long, long long> cnt;
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        auto it = cnt.find(target - x);
        if (it != cnt.end()) ans += it->second;
        ++cnt[x];
    }

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

同余配对计数

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

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

// Count pairs (i, j), i < j, with (a[i] + a[j]) % mod == 0.

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

    int n, mod;
    cin >> n >> mod;

    vector<long long> cnt(mod, 0);
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        int r = (int)((x % mod + mod) % mod);
        int need = (mod - r) % mod;
        ans += cnt[need];
        ++cnt[r];
    }

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

距离限制相等配对

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

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

// Count pairs (i, j), i < j, with a[i] == a[j] and j - i <= k.
// The map stores values inside the current left window [j-k, j-1].

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);

    unordered_map<long long, long long> cnt;
    long long ans = 0;

    for (int j = 0; j < n; ++j) {
        cin >> a[j];

        if (j > k) {
            long long expired = a[j - k - 1];
            auto it = cnt.find(expired);
            if (it != cnt.end()) {
                --it->second;
                if (it->second == 0) cnt.erase(it);
            }
        }

        auto it = cnt.find(a[j]);
        if (it != cnt.end()) ans += it->second;
        ++cnt[a[j]];
    }

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

距离限制最大配对和

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

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

// Given a[0..n-1], find max a[i] + a[j] with i < j and j - i <= k.
// Monotonic deque keeps candidate i with maximum a[i] in the current window.

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    deque<int> q;
    long long ans = LLONG_MIN;

    for (int j = 0; j < n; ++j) {
        while (!q.empty() && q.front() < j - k) q.pop_front();

        if (!q.empty()) {
            ans = max(ans, a[q.front()] + a[j]);
        }

        while (!q.empty() && a[q.back()] <= a[j]) q.pop_back();
        q.push_back(j);
    }

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

测试用例

黑白气球输入：

6
0 1 1 0 0 1

输出：

9

Two Sum 输入：

6 10
1 5 3 4 9 7

输出：

2

距离限制相等配对输入：

6 2
1 2 1 3 1 2

输出：

2

应用分类详解

配对问题的本质是“右端点枚举 + 左侧信息查询”。

一、属性配对

典型模式： 两个元素的类别满足相同、不同、互补等条件。

识别信号： 黑白、颜色、性别、类别、标签。

核心建模： 用桶记录左侧各类别数量。

应用场景 经典题目 核心思路
黑白气球 本页示例 当前是 0 就加左侧 1 的数量，当前是 1 就加左侧 0 的数量
同色配对 luogu-P1311 统计同色左端点，并处理额外有效性条件

二、数值配对

典型模式： 要求 ai+aj=Ka_i+a_j=K、ai−aj=Ka_i-a_j=K 或满足某个目标值。

识别信号： “两数之和”“差为 K”“找一对数”。

核心建模： 枚举 a[j]，在哈希表中查需要的另一半。

应用场景 经典题目 核心思路
Two Sum 计数 noiopenjudge ch0201-6184 查 target - a[j]
A-B=C 数对 luogu-P1102 固定一个端点，查另一个值出现次数

三、同余配对

典型模式： 两数和能被 k 整除。

识别信号： “整除”“余数”“mod k”。

核心建模： 当前余数为 r，需要左侧余数 (k-r)%k。

应用场景 经典题目 核心思路
和为 k 的倍数 同余配对基础题 用余数桶
分组配对 数论基础题 先按余数分类再计数

四、距离限制配对

典型模式： 配对还要求 j-i <= k。

识别信号： “距离不超过”“最近 k 个”“窗口内”。

核心建模： 只维护 [j-k, j-1] 这个窗口中的历史信息，过期元素要移除。

应用场景 经典题目 核心思路
窗口内同值配对 本页示例 add/remove/query 动态维护桶
选择客栈 luogu-P1311 条件有效后，把历史同色数量转为可配对数量

五、窗口最值配对

典型模式： 配对不是计数，而是求窗口内最大/最小值。

识别信号： “距离不超过 k 的最大两数和”“滑动窗口最大值”。

核心建模： 计数桶不适合维护最值，使用单调队列保留窗口内最强候选。

应用场景 经典题目 核心思路
滑动窗口最值 luogu-P1886 单调队列维护窗口最大/最小
距离限制最大配对和 本页模板 对每个 j，取窗口内最大 a[i]

经典例题

  • luogu-P1102 A-B 数对：数值配对计数。
  • luogu-P1311 选择客栈：属性配对叠加区间有效性。
  • luogu-P1886 滑动窗口：单调队列维护窗口最值。
  • noiopenjudge ch0201-6184 找和为 K 的两个元素：Two Sum 基础题。