Link

传送门

Problem

You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] or the value  - 1 if there is no such number.

Mean

给你长度为N的数组和M个查询,每次查询:数组下标在[l, r]内且值不为X的任意位置。

Analysis

本题普通直接查找的做法的极端情况是这一段内超多X,这样找起来就费时。那么我们可以针对这种情况打表,标记连续重复,设定查询跳转表。

Code

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

const int maxn = 204800;
int N, M, v[maxn], pa[maxn];
int L, R, X;

int Find() {
    for(int i = R; i >= L; ) {
        if(v[i] != X) return i;
        i = pa[i];
    }
    return -1;
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", v + i);
        if(v[i] == v[i-1]) pa[i] = pa[i-1];
        else pa[i] = i-1;
    }
    while(M--) {
        scanf("%d%d%d", &L, &R, &X);
        printf("%d\n", Find());
    }
    return 0;
}

欢迎留言