Codeforces 1927D题解报错求助：区间不同元素索引对逻辑问题

给定一个包含n个整数的数组a，以及q次查询。每次查询由两个整数l和r（1 ≤ l ≤ r ≤ n）表示，需找出满足以下条件的两个索引i和j（或判定不存在）：

• l ≤ i ≤ r
• l ≤ j ≤ r
• a[i] ≠ a[j]
  即需在区间a[l..r]中找到一对不同元素的索引，或报告不存在这样的对。

以下C++代码能通过给定测试用例，但无法通过隐藏测试用例，需要排查问题：

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

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned test; cin >> test; // Non-negative
    while (test--) {
        int size, query;
        cin >> size;
        vector<int> v(size), d;
        for (int &as : v) {
            cin >> as;
        }
        cin >> query;
        int x = -1;
        for (int i = 0; i < size; i++) {
            if (v[i] != x) {
                d.push_back(i + 1);
                x = v[i];
            }
        }
        while (query--) {
            int l, r;
            cin >> l >> r;
            int n , m;
            auto it = upper_bound(d.begin(), d.end(), l - 1);
            n = *it;
            if (n != l && n > l && n <= r) {
                cout << l << ' ' << n << endl;
            } else if (n == l && n <= r) {
                auto temp = upper_bound(d.begin(), d.end(), l);
                m = *temp;
                if (m <= r && m >= l) {
                    cout << n << ' ' << m << endl;
                } else {
                    cout << -1 << ' ' << -1 << endl;
                }
            } else {
                cout << -1 << ' ' << -1 << endl;
            }
        }
        cout << endl;
    }
    
    return 0;
}

1. 未处理迭代器越界 #

当upper_bound返回d.end()时，直接解引用*it会触发未定义行为（如程序崩溃）。例如：

• 当查询的l是d数组的最后一个元素时，temp = upper_bound(d.begin(), d.end(), l)会返回d.end()，此时m = *temp会访问非法内存。

2. 初始值冲突风险 #

预处理d数组时，初始x = -1，如果数组中存在-1这个值，会导致第一个元素无法被正确加入d数组。比如数组第一个元素是-1，v[0] != x的判断为假，d数组会缺失第一个元素的索引，后续所有逻辑都会出错。

3. 多余的换行输出 #

每个测试用例结束后输出cout << endl;，会产生多余的空行，不符合题目输出格式要求，可能导致判题系统误判。

4. 逻辑冗余与边界判断不严谨 #

部分条件判断重复（如n <= r在多个分支重复检查），且未覆盖所有边界场景，比如当区间内存在不同元素但d数组的下一个块刚好等于r时的判断。

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

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned test; cin >> test;
    while (test--) {
        int size, query_cnt;
        cin >> size;
        vector<int> v(size);
        for (int &val : v) {
            cin >> val;
        }
        cin >> query_cnt;
        
        // 预处理不同值的起始索引（1-based）
        vector<int> diff_starts;
        if (!v.empty()) {
            diff_starts.push_back(1);
            int prev_val = v[0];
            for (int i = 1; i < size; ++i) {
                if (v[i] != prev_val) {
                    diff_starts.push_back(i + 1);
                    prev_val = v[i];
                }
            }
        }
        
        while (query_cnt--) {
            int l, r;
            cin >> l >> r;
            
            // 找到第一个大于l-1的起始索引，即l所在或之后的第一个块
            auto it = upper_bound(diff_starts.begin(), diff_starts.end(), l - 1);
            if (it == diff_starts.end()) {
                cout << "-1 -1\n";
                continue;
            }
            
            int current_block = *it;
            if (current_block == l) {
                // 检查是否有下一个不同块在区间内
                auto next_it = next(it);
                if (next_it != diff_starts.end() && *next_it <= r) {
                    cout << l << ' ' << *next_it << '\n';
                } else {
                    // 区间内所有元素和a[l]相同
                    cout << "-1 -1\n";
                }
            } else {
                // current_block > l，说明l所在块的起始早于l，且current_block是下一个不同块的起始
                if (current_block <= r) {
                    cout << l << ' ' << current_block << '\n';
                } else {
                    cout << "-1 -1\n";
                }
            }
        }
    }
    
    return 0;
}

1. 迭代器越界处理：每次使用upper_bound后，先判断返回值是否为diff_starts.end()，避免非法解引用。
2. 修正预处理逻辑：初始化diff_starts时直接加入第一个元素的索引，后续从第二个元素开始比较，避免初始值与数组元素冲突。
3. 移除多余换行：删除测试用例结束后的空行输出，符合题目格式要求。
4. 简化逻辑：合并冗余判断，清晰区分不同块的位置关系，确保边界场景覆盖完整。

内容的提问来源于stack exchange，提问作者user27166005