hdu 5172 GTY's gay friends

时间：2021-05-07 22:04:02

GTY's gay friends

题意：给n个数和m次查询；(1<n,m<1000,000);之后输入n个数值(1 <= ai <= n)；问下面m次查询[L,R]中是否存在1~R-L+1的序列；

Sample Input
8 5
2 1 3 4 5 2 3 1
1 3
1 1
2 2
4 8
1 5
 
3 2
1 1 1
1 1
1 2
Sample Output
YES
NO
YES
YES
YES
 
YES
NO
 
分析:问区间是否存在1~R-L+1的排列；注意里面没有一个数相同，并且还都在[1,R-L+1]的区间内；可以等价 每个数前面出现的最大标号一定要小于L(保证了不重复)；其次输入的区间和要与结果的和相等；这样就确定了是在这个区间；
利用线段树维护区间pre[](每个点前面出现的最大标号)的最大值；着重理解里面的rt与区间的关系即可；
ps:这道题有更好的算法，使用线段树基本上都 2000+，我的代码2574MS  25448K  AC状态很不满意啊!!
 
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define inf 0x3f3f3f3f

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1|1

typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

const int MAXN = 1e6+;

int id[MAXN],mx[MAXN<<],pre[MAXN];

ll sum[MAXN];

void pushup(int rt)

{

    mx[rt] = max(mx[rt<<],mx[rt<<|]);

}

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

{

    if(l == r){

        mx[rt] = pre[l];

        return ;

    }

    int m = l + r >> ;

    build(lson);

    build(rson);

    pushup(rt);

}

int query(int L,int R,int l,int r,int rt)

{

    if(L <= l && r <= R){

        return mx[rt];

    }

    int m = l + r >> ,ret = ;

    if(L <= m) ret = max(ret,query(L,R,lson));

    if(R > m) ret = max(ret,query(L,R,rson));

    return ret;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m) == ){

        int x;

        fill(id,id+n+,);

        rep1(i,,n){

            sum[i] = ;

            read1(x);

            sum[i] += sum[i-] + x;

            pre[i] = id[x];

            id[x] = i;

        }

        build(,n,);

        int a,b;

        rep0(i,,m){

            read2(a,b);

            int len = b-a+;

            ll sm = (len+)*len/;

            if(sm != sum[b] - sum[a-]) puts("NO");

            else{

                int ret = query(a,b,,n,);

                //out(ret);

                puts(ret < a?"YES":"NO");

            }

        }

    }

    return ;

}
 
 

相关文章