hdu5172---GTY's gay friends - c++编程基础

TOP

hdu5172---GTY's gay friends

2015-07-20 17:16:29 来源: 作者: 【大中小】浏览:3次

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

Source
BestCoder Round #29

Recommend
hujie | We have carefully selected several similar problems for you: 5173 5169 5168 5165 5164

如果一个区间里是一个[1, … , r - l + 1]的排列，那么首先，区间和是
x * (x + 1) / 2， ?>前缀和处理
其次每一个数都不同，预处理每一个数上一次出现的位置pre，然后求出区间里pre的最大值，如果最大的pre小于左端点且区间和是 x * (x + 1) / 2，那么输出YES，否则NO，这里可以用线段树解决
注意判断时，最好先判断区间和，如果这里已经不满足了，就别去查询线段树了，否则容易造成TLE

/*************************************************************************
    > File Name: hdu5172.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年02月14日 星期六 12时49分13秒
 ************************************************************************/

#include  #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; const double pi = acos(-1); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
              
                PLL; const int N = 1000010; int pre[N]; LL sum[N]; int _hash[N]; struct node { int l, r; int val; }tree[N << 2]; void build (int p, int l, int r) { tree[p].l = l; tree[p].r = r; if (l == r) { tree[p].val = pre[l]; return; } int mid = (l + r) >> 1; build (p << 1, l, mid); build (p << 1 | 1, mid + 1, r); tree[p].val = max (tree[p << 1].val, tree[p << 1 | 1].val); } int query (int p, int l, int r) { if (tree[p].l == l && tree[p].r == r) { return tree[p].val; } int mid = (tree[p].l + tree[p].r) >> 1; if (r <= mid) { return query (p << 1, l, r); } else if (l > mid) { return query (p << 1 | 1, l, r); } else { return max (query (p << 1, l, mid), query (p << 1 | 1, mid + 1, r)); } } int main () { int n, m; while (~scanf("%d%d", &n, &m)) { memset (_hash, -1, sizeof(_hash)); memset (sum, 0, sizeof(sum)); int x, l, r; for (int i = 1; i <= n; ++i) { scanf("%d", &x); pre[i] = _hash[x]; _hash[x] = i; sum[i] = sum[i - 1] + (LL)x; } build (1, 1, n); while (m--) { scanf("%d%d", &l, &r); LL len = (LL)(r - l + 1); len = (len + 1) * len / 2; if (len != sum[r] - sum[l - 1]) { printf("NO\n"); continue; } int res = query (1, l, r); if (res < l) { printf("YES\n"); } else { printf("NO\n"); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu5174---Ferries Wheel	下一篇：hdu5171---GTY's birthday gi..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: