stl, 二分查找
题目意思：
有一个整数数组 a（元素最多 n <= 2e5）, 有 m 次查询 ，每次给出三个数 L, R, p;
要求在 坐标[L, R] 范围内，找到一个下标 k ，使得 a[k] != p 。每次输出k， 如果找不到，就输出 -1;
本题要点：
1、 vector v[MaxN];
用 vector 数组a的每一个数 a[i] 在数组a中的下标。 v[a[i]].push_back(i);
然后 在 v[a[i]] 里面，存的所有下标是从小到大排序的。 有序后就可以二分了。
2、一些特判。
如果 L == R， 直接看 a[L] 是否等于 p;
如果 v[p].size() == 0, 说明p根本不在a数组出现，直接输出 L;
如果 v[p].size() == 0, 并且 L < R 的情况，看看 a[L], a[R] 与 p的关系即可。
还有看看 [L, R]是否在 p 的所有的下标范围内，如果 [L, R] 超出了其范围，看看L 和 v[p][0]，
R和 v[p][len - 1] 的关系即可判断。
3、普遍的情况
v[p][0] <= L && R <= v[p][len - 1]。 [L, R]在 p 的所有的下标范围内。
用 lower_bound 分别找到 L, R 在 v[p] 中出现的下标 dx ， dy;
如果， p 在数组a中的 [L, R] 的范围内都出现， 必然有 v[dx] == L && v[dy] == R, 并且 R - L == dy - dx;
如果不是连续出现，满足 v[dx] == L && v[dy] == R, 而 R - L > dy - dx, 需要找到第一个 a[k] != p 的下标，
使用二分查找， 在v[p] 中，[dx, dy] 范围内，找到第一个 满足 v[p][k] - k > L - dx 的 k 坐标。
v[p][k] - 1 , 肯定是满足 a[k] != p 的下标。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MaxN = 1e6 + 10;
int a[MaxN];
int n, m;
int l, r, p;
vector<int> v[MaxN];int solve()
{
if(l == r){
if(a[l] == p) return -1;else return l;}int len = v[p].size();if(0 == len)return l;if(len == 1){
if(a[l] != p) return l;if(a[r] != p) return r;}if(v[p][0] > l) return l;if(v[p][len - 1] < r) return r;int dx = lower_bound(v[p].begin(), v[p].end(), l) - v[p].begin();if(v[p][dx] != l) return l; int dy = lower_bound(v[p].begin(), v[p].end(), r) - v[p].begin(); if(v[p][dy] != r) return r;if(dy - dx == r - l) return -1;int step = l - dx;int L = dx, R = dy, mid = 0;while(L < R){
mid = (L + R) / 2; if(v[p][mid] - mid > step){
R = mid; }else{
L = mid + 1;}}return v[p][L] - 1;
}int main()
{
scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);v[a[i]].push_back(i);}for(int i = 0; i < m; ++i){
scanf("%d%d%d", &l, &r, &p);printf("%d\n", solve());}return 0;
}/* 6 4 1 2 1 1 3 5 1 4 1 2 6 2 3 4 1 3 4 2 *//* 2 6 -1 4 */