Problem Description

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.

Input

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.

Output

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.

Sample Input

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

Sample Output

2
6
-1
4

題意：給出 n 個數 m 組詢問，每組詢問 l、r、x，任意輸出區間 [l,r]?上不等于 x 的一個位置，若在區間內全等于 x，則輸出 -1?

思路：有些類似并查集路徑壓縮的思想，開一個數組 res[]，令 res[i] 記錄第 i? 個數前面第一個和他不等的數的下標就行了，如果相等就令 res[i]=res[i-1]，然后每次對 [l,r] 查詢時，從最右端開始與 x 對比即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-6 #define MOD 1000000007 #define INF 0x3f3f3f3f #define N 1001 #define LL long long using namespace std; int a[N]; int res[N]; int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&a[i]);res[n]=n;for(int i=n-1;i>=1;i--){if(a[i]==a[i+1])res[i]=res[i+1];elseres[i]=i;}while(m--){int l,r,x;scanf("%d%d%d",&l,&r,&x);if(a[l]!=x)printf("%d\n",l);else if(res[l]+1<=r)printf("%d\n",res[l]+1);elseprintf("-1\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的Not Equal on a Segment（CF-622C）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。