题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5172

题意：给出n个数，m个询问，问你[l,r]区间内是否为1到r-l+1的全排列。 大小很容易我们通过记录前缀和很容易求出来，但是关键是去重。 考虑线段树做法，我们记录每个点的靠左最近的相同元素的位置，然后求 整个区间的最大值（即最大的前驱）如果小于l,即满足条件，输出YES。

好吧，其实这个题目我是搜的RMQ算法出来的，因为我想练一下RMQ算法，所以我就看了一下别人的博客，自己也写了一下，结果死活MLE。。。

好吧，我仔细看了一下，1000000的数据量用RMQ开一个二维数组1000000*20，显然会超内存。。。

结果我不得不老老实实的滚回去用线段树写了。。。orz....

RMQ的MLE代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
#define inf 1<<30
#define sf(a) scanf("%d",&a);
#define CLEAR(a,b) memset(a,b,sizeof(a))
using namespace std;
/*
    TLE...显然超内存；
*/
const int N=1000005;
int n,m,a,b;
int num[N],pre[N];
int dp[N][21];
int sum[N];
void ST(int len)
{
    for(int i=1;i<=n;i++) dp[i][0]=num[i];
    for(int j=1;1<<j < n;j++){
        for(int i=1;i+(1<<j)-1<n;i++){
            dp[i][j]=max(dp[i][j-1],dp[i+1<<(j-1)][j-1]);
        }
    }
}
int rmq(int s,int v)
{
    int k=(int)(log(v-s+1)*1.0/log(2.0));
    return max(dp[s][k],dp[v-1<<k+1][k]);
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        CLEAR(pre,0);
        CLEAR(sum,0);
        for(int i=1;i<=n;i++){
            sf(a);
            sum[i]+=sum[i-1]+a;
            num[i]=pre[a];
            pre[a]=i;
        }
        ST(n);
        while(m--){
            sf(a);sf(b);
            double tmp=(b-a+2)*(b-a+1)*1.0/2.0;
            if(tmp!=sum[b]-sum[a-1]){
                //cout<<tmp<<' '<<sum[b]-sum[a-1]<<' ';
                printf("NO\n");
                continue;
            }else{
                if(rmq(a,b)<a) printf("YES\n");
                else printf("NO\n");
            }
        }
    }
    return 0;
}

线段树AC代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
#define inf 1<<30
#define s(a) scanf("%d",&a)
#define CLEAR(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1000005;
int n,m,a,b;
int pre[N],sum[N];  //  sum存总和，pre定位该数字上一次出现的位置；
struct node
{
    int l,r;
    int pre;    //  用线段树维护最近一个重复的数字；
}node[N<<2];
void PushUp(int rt)
{
    node[rt].pre=max(node[rt<<1].pre,node[rt<<1|1].pre);
}
void build(int l,int r,int rt)
{
    node[rt].l=l;
    node[rt].r=r;
    node[rt].pre=0;
    if(l!=r){
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
    }
}
void Insert(int v,int p,int rt)
{
    int ll=node[rt].l,rr=node[rt].r;
    if(ll==rr&&p==ll){
        node[rt].pre=pre[v];
        return;
    }
    int mid=(ll+rr)>>1;
    if(p<=mid) Insert(v,p,rt<<1);
    else Insert(v,p,rt<<1|1);
    PushUp(rt);
}
int query(int l,int r,int rt)
{
    int ll=node[rt].l,rr=node[rt].r;
    if(ll==l&&rr==r){
        return node[rt].pre;
    }
    int mid=(ll+rr)>>1;
    if(r<=mid) return query(l,r,rt<<1);
    else if(l>mid) return query(l,r,rt<<1|1);
    else return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
}
int main()
{
    while(~s(n)){
        s(m);
        CLEAR(pre,0);
        CLEAR(sum,0);
        build(1,n,1);
        for(int i=1;i<=n;i++){
            s(a);
            sum[i]+=sum[i-1]+a;
            Insert(a,i,1);
            pre[a]=i;
        }
        while(m--){
            s(a);s(b);
            int tmp=(b-a+2)*(b-a+1)*1.0/2.0;    //  如果是全排列那么最后的和必然符合这个公式；
            if(sum[b]-sum[a-1]!=tmp){
                printf("NO\n");
                continue;
            }else{
                if(query(a,b,1)<a) printf("YES\n"); //  查询该区间最近一个重复的数字出现的位置，如果比a小，那就说明这个区间没有出现过重复的数字；
                else printf("NO\n");
            }
        }
    }
    return 0;
}

//CodeForces 91B Queue 线段树 单点更新 成段查询
/*
题目地址：http://codeforces.com/problemset/problem/91/B

题意：
有n个数的失望值，
失望值的定义是：离它最远的比它小的数 与 它本身之间 间隔的数的数量

思路：
线段树，结点保存区间最小值
每次将当前的数更新为INF，然后查找整个区间内最右边的比它小的数的下标

*/

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define INF 1000000005
#define N 100005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

int mmin[N<<2],s[N];

int Min(int x,int y){
	return x<y?x:y;
}

void Pushup(int rt){
	mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
}

void Build(int rt,int l,int r){
	if(l == r){
		scanf("%d",&mmin[rt]);
		s[l] = mmin[rt];
		return ;
	}
	int mid = (l + r) >> 1;
	Build(lson);
	Build(rson);
	Pushup(rt);
}

void Update(int rt,int l,int r,int x){
	if(l == r){
		mmin[rt] = INF;
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) Update(lson,x);
	else		 Update(rson,x);
	Pushup(rt);
}

int Query(int rt,int l,int r,int x){
	if(l == r)
		return l;
	int mid = (l + r) >> 1;
	if(mmin[rt<<1|1] < x) return Query(rson,x);
	else			  return Query(lson,x);
}

int main(){
	int n,i;
	while(scanf("%d",&n)!=EOF){
		Build(1,1,n);
		for(i = 1; i <= n; ++i){
			Update(1,1,n,i);

			if(mmin[1] >= s[i])
				printf("%d%c",-1,i==n?'\n':' ');
			else
				printf("%d%c",Query(1,1,n,s[i])-i-1,i==n?'\n':' ');
		}
	}
	return 0;
}

线段树是一种强（傻）大（逼）的数据结构，但博主实在是无聊，只好默默的玩一下这种强（傻）大（逼）的数据结构（博主N年前就已经掌握了这种数据结构）。但博主为了共产（工厂）主义事业，终于写下了这个代码（为NOIPPJ的水题奋斗）。

/*************************************************************************
    > File Name: \LJF\数据结构\树\线段树\单点更新模板.cpp
    > Author: ljf_cnyali
    > Mail: ljfcnyali@gmail.com 
    > Last modifiedz: 2017-02-2 11:49
    > Description: This is a large group of God's program information.
 ************************************************************************/

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>

using namespace std;

#define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
#define mem(a) memset((a), 0, sizeof(a))
#define str(a) strlen(a)
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1

const int maxn = 10000;

int n, m;

int Tree[maxn << 2];

void pushup(int rt) {
    Tree[rt] = Tree[rt << 1] + Tree[rt << 1 | 1];   
}

void Bulid(int l, int r, int rt) {
    if(l == r) {
        Tree[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    Bulid(lson);
    Bulid(rson);
    pushup(rt);
}

void update(int pos, int val, int l, int r, int rt) {
    if(l == r) {
        Tree[rt] += val;
        return;
    }   
    int mid = (l + r) >> 1;
    if(pos <= mid)
        update(pos, val, lson);
    else
        update(pos, val, rson);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if(L <= r && r <= R)
        return Tree[rt];
    int mid = (l + r) >> 1;
    int ret = 0;
    if(L <= mid)
        ret += query(L, R, lson);
    if(R > mid)
        ret += query(L, R, rson);
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif


    return 0;
}