题目总结与题解

题目概述

给定 n 个点，每个点有两个属性 (a_i) 和 (b_i)。当且仅当满足以下条件之一时，点 i 和 j（(i < j)）之间有边：

(a_i - a_j \leq i - j \leq b_i - b_j)
(a_j - a_i \leq j - i \leq b_j - b_i)

求图中的连通分量数量。

关键思路

条件转换

定义 (x_i = a_i - i) 和 (y_i = i - b_i)。点 i 和 j（(i < j)）连通的条件简化为：(x_i \leq x_j \quad \text{且} \quad y_i \leq y_j)

排序优化

将所有点按 (x_i) 从小到大排序，(x_i) 相同时按 (y_i) 从小到大排序。排序后，对于任意 (i < j)，有 (x_i \leq x_j)，此时只需关注 (y_i) 的单调性。

单调栈维护

使用单调栈维护当前所有连通块的最小 y 值。

当处理一个新点时，若其 y 值大于等于栈顶的 y 值，则合并栈顶连通块，直到栈顶的 y 值严格大于当前点的 y 值。
最终栈的大小即为连通分量的数量。

AC 代码

cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<PII> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x - (i + 1), (i + 1) - y};  // 注意点编号从1开始
    }
    
    sort(a.begin(), a.end());
    stack<PII> stk;
    
    for (int i = 0; i < n; i++) {
        int x = a[i].first, y = a[i].second;
        
        if (stk.empty() || y < stk.top().second) {
            stk.push(a[i]);
        } else {
            PII minx = stk.top();
            while (!stk.empty() && stk.top().second <= y) {
                stk.pop();
            }
            stk.push(minx);
        }
    }
    
    cout << stk.size() << endl;
    return 0;
}

代码解析

输入处理

将每个点转换为 ((x_i, y_i) = (a_i - i, i - b_i))。注意点编号从 1 开始（代码中 (i+1) 对应实际编号）。

排序

按 (x_i) 升序排序，(x_i) 相同时按 (y_i) 升序排序。

单调栈逻辑

新点入栈条件：若当前点的 y 值小于栈顶的 y，直接入栈（形成新连通块）。
合并条件：若当前点的 y 值大于等于栈顶的 y，弹出所有 (y \leq) 当前 y 的栈顶元素，最后将栈顶的最小 y 保留（合并连通块）。

时间复杂度

排序：(O(n \log n))
单调栈处理：(O(n)) 总时间复杂度为 (O(n \log n))，适用于 (n \leq 10^6)。

示例验证

输入样例

处理过程

转换为

：
- 点 1：(x = 1 - 1 = 0), (y = 1 - 5 = -4)
- 点 2：(x = 2 - 2 = 0), (y = 2 - 3 = -1)
- 点 3：(x = 2 - 3 = -1), (y = 3 - 4 = -1)
排序后顺序：((-1, -1)), ((0, -4)), ((0, -1))
栈操作

：
- ((-1, -1)) 入栈 → 栈：([(-1, -1)])
- ((0, -4))：(y <) 栈顶 → 入栈 → 栈：([(-1, -1), (0, -4)])
- ((0, -1))：(y \geq) 栈顶 → 弹出栈顶，保留 ((-1, -1)) → 栈：([(-1, -1)])
输出：1（正确）。