题目链接：

http://codeforces.com/problemset/problem/622/C

题意：

给定序列，若干查询，每个查询给定区间和t，输出区间内任意一个不等于t的元素的位置。

分析：

最初没看样例直接钦定输出每个不等于t的元素位置，结果怎么想都是n2复杂度的，后来看了样例才发现是输出任意一个。。

对于一个区间，如果区间最大值和最小值相等，那么该区间元素值全部相同，那么我们维护区间的最大最小值，然后判断是否均等于t，若不等，输出最大值或最小值的位置即可，若相等， 则该区间所有元素值均等于t。

区间最大最小值用线段树维护，最初使用map来保存最大最小值所在的位置，结果TLE，改成数组就过了，就是内存难看了一点。。

感觉自己姿势怪怪的上网搜了一发标程：设dp[i]表示不等于a[i]的最大的元素下标

这样每次看t是否等于区间最右端的值，若是，则判断dp[t]是否在区间内，若不是，则最右端的值即为答案。非常巧妙。

代码：

#include<iostream>

#include<cstdio>

#include<map>

using namespace std;

#define sa(n) scanf("%d", &(n))

const int maxn = 6e5 + 5, maxm = 1e6 + 5, oo = 0x3f3f3f3f;

struct Node{int l;int r;int a; int b;int pa;int pb;}Tree[maxn];

int a[maxn];

int ans[maxm];

void build(int i, int l, int r)

{

    Tree[i].l = l;

    Tree[i].r = r;

    Tree[i].a = 0;

    Tree[i].b = oo;

    if(l == r) {

            Tree[i].pa =  Tree[i].pb = l;

            return;

    }

    int mid = l + r >> 1;

    build(i << 1, l, mid);

    build((i << 1) | 1, mid + 1, r);

}

void push_up(int i)

{

    if(Tree[i<<1].a > Tree[(i << 1)| 1].a){

        Tree[i].a = Tree[i<<1].a ;

        Tree[i].pa = Tree[i << 1].pa;

    }else{

        Tree[i].a = Tree[(i<<1) | 1].a ;

        Tree[i].pa = Tree[(i << 1) | 1].pa;

    }

    if(Tree[i<<1].b < Tree[(i << 1)| 1].b){

        Tree[i].b = Tree[i<<1].b ;

        Tree[i].pb = Tree[i << 1].pb;

    }else{

        Tree[i].b = Tree[(i<<1) | 1].b ;

        Tree[i].pb = Tree[(i << 1) | 1].pb;

    }

}

int querymax(int i, int l, int r)

{

    if(Tree[i].l == l && Tree[i].r == r){

        ans[Tree[i].a]  = Tree[i].pa;

        return Tree[i].a;

    }

    int mid = Tree[i].l + Tree[i].r >> 1;

    if(r <= mid) return querymax(i<<1, l, r);

    else if(l > mid) return querymax((i << 1)|1, l, r);

    else return max(querymax(i << 1, l, mid), querymax((i << 1)|1, mid + 1, r));

}

int querymin(int i, int l, int r)

{

    if(Tree[i].l == l && Tree[i].r == r){

        ans[Tree[i].b] = Tree[i].pb;

        return Tree[i].b;

    }

    int mid = Tree[i].l + Tree[i].r >> 1;

    if(r <= mid) return querymin(i<<1, l, r);

    else if(l > mid) return querymin((i << 1)|1, l, r);

    else return min(querymin(i << 1, l, mid), querymin((i << 1)|1, mid + 1, r));

}

void update(int i, int k, int x)

{

    if(Tree[i].l == k && Tree[i].r == k){

        Tree[i].a =  Tree[i].b = x;

        return;

    }

    int mid = Tree[i].l + Tree[i].r >> 1;

    if(k <= mid) update(i << 1, k, x);

    else update((i << 1) | 1, k, x);

    push_up(i);

}

int main (void)

{

    int n, m;sa(n);sa(m);

    build(1, 0, n - 1);

    for(int i = 0; i < n; i++){

        sa(a[i]);

        update(1, i, a[i]);

    }

    int l, r, x;

    int a, b;

    for(int i = 0; i < m; i++){

        sa(l);sa(r);sa(x);

        a = querymax(1, l - 1, r - 1);

        b = querymin(1, l - 1, r - 1);

        if(a == b && a == x) puts("-1");

        else if(a == x) printf("%d\n", ans[b] + 1);

        else printf("%d\n", ans[a] + 1);

    }

    return 0;

}

DP方法

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define sa(n) scanf("%d", &(n))

const int maxn = 6e5 + 5, maxm = 1e6 + 5, oo = 0x3f3f3f3f;

int dp[maxn];

int a[maxn];

int main (void)

{

    int n, m;sa(n);sa(m);

    memset(dp, -1, sizeof(dp));

    for(int  i = 1; i <= n; i++){

        sa(a[i]);

        if(a[i] == a[i - 1]) dp[i] = dp[i - 1];

        else dp[i] = i - 1;

    }

    int l, r, t;

    for(int i = 0; i < m; i++){

        sa(l);sa(r);sa(t);

        if(a[r] == t){

            if(dp[r] < l) cout<<-1<<endl;

            else cout<<dp[r]<<endl;

        }else cout<<r<<endl;

    }

    return 0;

}