GTY’s gay friends

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

GTY has n gay friends. To manage them conveniently, every morning he ordered all his gay friends to stand in a line. Every gay friend has a characteristic value ai , to express how manly or how girlish he is. You, as GTY’s assistant, have to answer GTY’s queries. In each of GTY’s queries, GTY will give you a range [l,r] . Because of GTY’s strange hobbies, he wants there is a permutation [1..r−l+1] in [l,r]. You need to let him know if there is such a permutation or not.

Input

Multi test cases (about 3) . The first line contains two integers n and m ( 1≤n,m≤1000000 ), indicating the number of GTY’s gay friends and the number of GTY’s queries. the second line contains n numbers seperated by spaces. The ith number ai ( 1≤ai≤n ) indicates GTY’s ith gay friend’s characteristic value. The next m lines describe GTY’s queries. In each line there are two numbers l and r seperated by spaces ( 1≤l≤r≤n ), indicating the query range.

Output

For each query, if there is a permutation [1..r−l+1]
in [l,r], print ‘YES’, else print ‘NO’.

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

题意

给出一个数列，询问连续的从l开始到r为止的数是否刚好能够组成从1开始到r-l+1的数列。

分析

每一次询问都是一个区间询问。

对于每一个区间询问，需要判断区间内的数是否刚好可以组成1到k的连续数列，主要的判断标准有两个：

1.区间数字的总和与（1+k）*k/2相等；

2.保证区间内所有数都只出现一次。

第一个可以在读入数据时用前缀和解决。

第二个就要用到线段树了，读入时预处理记录下与当前数相同的数最近一次出现的位置。询问l~r的区间时，检索每个数的最近出现位置位置，若得到的所有结果都在区间左端的左边，那就说明区间中所有的数都是不重复出现的，则满足条件。这里就是用线段树判断区间最大值小于区间左端的过程了

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU5172
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e6+10;

int last[N],a,sum[N];
 
typedef struct treetyp
{
    int a,b,l,r,data;
} treetype;
treetype tree[2*N];
int treetail;

void maketree(int l,int r)
{
    treetail++;
    int now=treetail;
    tree[now].a=l;
    tree[now].b=r;
    if (l<r)
    {
        tree[now].l=treetail+1;
        maketree(l,(l+r)/2);
        tree[now].r=treetail+1;
        maketree((l+r)/2+1,r);
    }
}

void add(int n,int i,int data)
{
    if (tree[n].data<data) tree[n].data=data;
    if (i==tree[n].a&&i==tree[n].b) return ;
    else if (i<=(tree[n].a+tree[n].b)/2) add(tree[n].l,i,data);
         else add(tree[n].r,i,data);
}

int res;

void search(int n,int a,int b)
{
    if (tree[n].a>=a&&tree[n].b<=b)
    {
        if (res<tree[n].data) res=tree[n].data;
        return ;
    }
    if (tree[n].a==tree[n].b) return ;
    if (a<=(tree[n].a+tree[n].b)/2) search(tree[n].l,a,b);
    if (b>=(tree[n].a+tree[n].b)/2+1) search(tree[n].r,a,b);
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(sum,0,sizeof(sum));
        memset(last,0,sizeof(last));

        treetail=0;
        maketree(1,n);
        for (int i=1;i<=n;i++) 
        {
            scanf("%d",&a);
            sum[i]=sum[i-1]+a;
            add(1,i,last[a]);
            last[a]=i;
        }

        for (int i=1;i<=m;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if ((r-l+1)*(r-l+2)/2==sum[r]-sum[l-1])
            {
                res=0;
                search(1,l,r);
                if (res<l) printf("YES\n");
                else printf("NO\n");
            } else printf("NO\n");
        }
    }

    return 0;
}

Chenfan Blog

HDU 5172 GTY's gay friends 线段树