#5459. 「ROI 2012 Day 2」马赛克 题解

问题分析

我们有 $N$ 个矩形元素，每个元素有长度 $A_i$ 和宽度 $B_i$。
两个元素是不和谐对当且仅当：

• $A_i \neq A_j$ 且 $B_i \neq B_j$

换句话说，两个元素和谐当且仅当它们至少有一个维度相同。

我们需要回答 $K$ 个区间查询 $[N_1, N_2]$，找到区间内的任意一个不和谐对，或者报告不存在。

关键观察

1. 不和谐对条件：$(A_i, B_i)$ 和 $(A_j, B_j)$ 是不和谐对 ⇔ $A_i \neq A_j$ 且 $B_i \neq B_j$

2. 数据结构需求：我们需要快速回答多个区间查询

3. 寻找任意解：只需要找到一个不和谐对，不需要找所有

算法思路

方法1：预处理所有相邻不和谐对（适用于小数据）

对于 $N \leq 5000$ 的情况：

• 预处理所有相邻元素是否构成不和谐对
• 对于查询 $[l, r]$，检查区间内是否存在相邻不和谐对
• 时间复杂度：$O(N^2 + K)$

方法2：基于排序和扫描（适用于大数据）

更高效的方法：

1. 按 $A$ 排序：将元素按 $A_i$ 排序，记录原位置
2. 按 $B$ 排序：将元素按 $B_i$ 排序，记录原位置
3. 对于每个查询：
   • 如果区间内存在两个元素在 $A$ 排序中相邻且原位置都在区间内，且 $B$ 值不同 → 找到解
   • 如果区间内存在两个元素在 $B$ 排序中相邻且原位置都在区间内，且 $A$ 值不同 → 找到解

方法3：随机化+检查候选对

由于只需要找到任意一个不和谐对，可以：

1. 对于每个查询，随机选择几个元素对检查
2. 如果随机检查失败，再用更复杂的方法

高效算法

核心思想：最近不同值查询

对于每个位置 $i$，预处理：

• $nextA[i]$：下一个 $A$ 值不同的位置
• $nextB[i]$：下一个 $B$ 值不同的位置

那么对于查询 $[l, r]$：

• 如果存在 $i \in [l, r]$ 使得 $nextA[i] \leq r$ 且 $B[i] \neq B[nextA[i]]$，则 $(i, nextA[i])$ 是不和谐对
• 如果存在 $i \in [l, r]$ 使得 $nextB[i] \leq r$ 且 $A[i] \neq A[nextB[i]]$，则 $(i, nextB[i])$ 是不和谐对

算法步骤

1. 预处理 $nextA$ 和 $nextB$ 数组
2. 构建数据结构快速查询区间内是否存在满足条件的 $i$
3. 回答查询：对于每个查询 $[l, r]$，在区间内查找第一个满足条件的 $i$

复杂度分析

• 预处理：$O(N \log N)$ 排序
• 每个查询：$O(\log N)$ 使用线段树/RMQ
• 总复杂度：$O((N+K) \log N)$

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 100005;

int n, k;
int A[MAXN], B[MAXN];
int nextA[MAXN], nextB[MAXN];

// 线段树查询区间最小值
struct SegmentTree {
    vector<int> tree;
    int size;
    
    SegmentTree(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, MAXN);
    }
    
    void update(int idx, int val) {
        idx += size;
        tree[idx] = val;
        for (idx /= 2; idx >= 1; idx /= 2) {
            tree[idx] = min(tree[2*idx], tree[2*idx+1]);
        }
    }
    
    int query(int l, int r) {
        l += size;
        r += size;
        int res = MAXN;
        while (l <= r) {
            if (l % 2 == 1) res = min(res, tree[l++]);
            if (r % 2 == 0) res = min(res, tree[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i];
    }
    
    // 预处理 nextA 和 nextB
    vector<pair<int, int>> sortedA(n), sortedB(n);
    for (int i = 1; i <= n; i++) {
        sortedA[i-1] = {A[i], i};
        sortedB[i-1] = {B[i], i};
    }
    
    sort(sortedA.begin(), sortedA.end());
    sort(sortedB.begin(), sortedB.end());
    
    // 初始化 next 数组
    for (int i = 1; i <= n; i++) {
        nextA[i] = nextB[i] = n + 1;
    }
    
    // 计算 nextA
    for (int i = 0; i < n - 1; i++) {
        int idx1 = sortedA[i].second;
        int idx2 = sortedA[i+1].second;
        if (sortedA[i].first != sortedA[i+1].first) {
            nextA[min(idx1, idx2)] = max(idx1, idx2);
        }
    }
    
    // 计算 nextB
    for (int i = 0; i < n - 1; i++) {
        int idx1 = sortedB[i].second;
        int idx2 = sortedB[i+1].second;
        if (sortedB[i].first != sortedB[i+1].first) {
            nextB[min(idx1, idx2)] = max(idx1, idx2);
        }
    }
    
    // 构建线段树
    SegmentTree segA(n+1), segB(n+1);
    for (int i = 1; i <= n; i++) {
        segA.update(i, nextA[i]);
        segB.update(i, nextB[i]);
    }
    
    cin >> k;
    while (k--) {
        int l, r;
        cin >> l >> r;
        
        // 检查是否存在不和谐对
        bool found = false;
        
        // 检查通过A不同的对
        int minNextA = segA.query(l, r);
        if (minNextA <= r) {
            for (int i = l; i <= r; i++) {
                if (nextA[i] <= r && B[i] != B[nextA[i]]) {
                    cout << i << " " << nextA[i] << "\n";
                    found = true;
                    break;
                }
            }
        }
        
        if (found) continue;
        
        // 检查通过B不同的对
        int minNextB = segB.query(l, r);
        if (minNextB <= r) {
            for (int i = l; i <= r; i++) {
                if (nextB[i] <= r && A[i] != A[nextB[i]]) {
                    cout << i << " " << nextB[i] << "\n";
                    found = true;
                    break;
                }
            }
        }
        
        if (!found) {
            cout << "0 0\n";
        }
    }
    
    return 0;
}