题目描述

难度分:$1700$

输入$n(1 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$和长为 $n$的数组$a(1 \leq a[i] \leq 10^6)$。

然后输入$m$个询问，每个询问输入三个数$L$，$R$，$x(1 \leq x \leq 10^6)$。下标从$1$开始。

对于每个询问，输出任意$i$，满足$i$在闭区间$[L,R]$内且$a[i] \neq x$。

如果不存在这样的$i$，输出$-1$。

输入样例

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

输出样例

2
6
-1
4

算法

$RMQ$预处理+二分查找

比较容易想到思路，先构建一个映射$val2pos$表示“数值$\rightarrow$索引列表”。

然后考察每条询问$(l,r,x)$，先判断$val2pos$中是不是有$x$：

1. 没有就说明整个数组都没有$x$，随便输出一个$[l,r]$内的索引即可，输出$l$。
2. 否则查询区间$[l,r]$的最大值$mx$和最小值$mn$，$mn=mx$就看这个值是不是$x$，是就说明整个子数组$[l,r]$都是$x$，不存在$a[i] \neq x$的位置，输出$-1$。否则考察$x$是不是最值，如果$x=mn$就取出$pos=val2pos[mx]$，如果$x=mx$就取出$pos=val2pos[mn]$，在$pos$上二分查找落在$[l,r]$内的一个索引即可。

此时还剩下一个关键问题，流程中存在查询区间最值的操作，如何来做？由于自始至终数组$a$都没有被修改过，因此用$RMQ$做个预处理，这样就可以$O(1)$查询区间最值了。

复杂度分析

时间复杂度

$RMQ$预处理的时间复杂度为$O(nlog_2U)$，其中$U$是$a$数组的值域。每个询问需要在最差情况下需要进行常数次二分查找，时间复杂度为$O(mlog_2n)$。因此，整个算法的时间复杂度为$O(nlog_2U+mlog_2n)$。

空间复杂度

空间消耗在于区间最值的两个$st$表，额外空间为$O(nlog_2U)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 21;
int n, m, a[N], st_min[N][M], st_max[N][M];

int 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]);
}

int 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]);
}

int main() {
    scanf("%d%d", &n, &m);
    map<int, vector<int>> val2pos;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        val2pos[a[i]].push_back(i);
    }
    // 区间max
    for(int j = 0; j < M; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            if(!j) {
                st_max[i][j] = a[i];
            }else {
                st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1<<(j - 1))][j - 1]);
            }
        }
    }

    // 区间min
    for(int j = 0; j < M; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            if(!j) {
                st_min[i][j] = a[i];
            }else {
                st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1<<(j - 1))][j - 1]);
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        if(!val2pos.count(x)) {
            // 整个数组都没有x
            printf("%d\n", l);
        }else {
            auto& pos = val2pos[x];
            int index = upper_bound(pos.begin(), pos.end(), r) - pos.begin();
            if(index > 0 && pos[--index] >= l) {
                // [l,r]中存在x
                int mn = query_min(l, r), mx = query_max(l, r);
                if(mn == mx) {
                    // 区间内全是x
                    puts("-1");
                }else {
                    if(mn != x) {
                        auto& pos = val2pos[mn];
                        auto itl = lower_bound(pos.begin(), pos.end(), l);
                        printf("%d\n", *itl);
                    }else {
                        auto& pos = val2pos[mx];
                        auto itl = lower_bound(pos.begin(), pos.end(), l);
                        printf("%d\n", *itl);
                    }
                }
            }else {
                // [l,r]中不存在x
                printf("%d\n", l);
            }
        }
    }
    return 0;
}