题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^6)$，下标从$1$开始。

然后输入$q(1 \leq q \leq 2 \times 10^5)$和$q$个询问，每个询问输入两个数$L$、$R(1 \leq L \lt R \leq n)$。

对于每个询问，输出在$[L,R]$内的两个下标$i$和$j$，满足$a[i] \neq a[j]$。如果不存在，输出-1 -1。

输入样例

5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5

输出样例

2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4

算法

RMQ+二分

首先将目标定位为找到区间的最大值和最小值，如果这两个值是相等的，那么区间内就只有一种数，直接打印-1 -1。否则就获得一个最大值的索引和一个最小值的索引，我们可以预处理出一个映射“数值$\rightarrow$索引列表”$val2pos$，在两个最值对应的索引列表上二分找到$\geq L$的最小索引拿出来当答案即可。

而由于整个数组是不经过修改的，因此本问题是个静态问题，倍增预处理出区间最值的两个$ST$表，便于每个询问$O(1)$查询区间最值。

复杂度分析

时间复杂度

倍增预处理的时间复杂度为$O(nlog_2m)$，其中$m$是$a[i]$的值域范围。接下来每条查询，先要$O(1)$查询区间最值，在有解的情况下还要进行$O(log_2n)$的二分查找，时间复杂度为$O(qlog_2n)$。因此，整个算法的时间复杂度为$O(nlog_2m+qlog_2n)$。

空间复杂度

“数值$\rightarrow$索引位置列表”的哈希表存了$O(n)$级别的索引，空间复杂度为$O(n)$。因此，空间的瓶颈在于区间最值的两个$ST$表，整个算法的额外空间复杂度为$O(nlog_2m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010, M = 20;
int T, n, q, a[N], st_max[N][M], st_min[N][M];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        unordered_map<int, vector<int>, custom_hash> val2pos;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            val2pos[a[i]].push_back(i);
        }
        for(int j = 0; j < M; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                if(!j) {
                    st_max[i][j] = st_min[i][j] = a[i];
                }else {
                    st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1<<(j - 1))][j - 1]);
                    st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1<<(j - 1))][j - 1]);
                }
            }
        }
        auto query_max = [&](int l, int r) {
            int k = log2(r - l + 1);
            return max(st_max[l][k], st_max[r - (1<<k) + 1][k]);
        };
        auto query_min = [&](int l, int r) {
            int k = log2(r - l + 1);
            return min(st_min[l][k], st_min[r - (1<<k) + 1][k]);
        };
        scanf("%d", &q);
        while(q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            int mx = query_max(l, r), mn = query_min(l, r);
            if(mx == mn) {
                puts("-1 -1");
            }else {
                int index1 = val2pos[mx][lower_bound(val2pos[mx].begin(), val2pos[mx].end(), l) - val2pos[mx].begin()];
                int index2 = val2pos[mn][lower_bound(val2pos[mn].begin(), val2pos[mn].end(), l) - val2pos[mn].begin()];
                if(index1 > index2) swap(index1, index2);
                printf("%d %d\n", index1, index2);
            }
        }
        puts("");
    }
    return 0;
}