程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5172 GTY's gay friends（線段樹）

HDU 5172 GTY's gay friends（線段樹）

編輯：關於C++

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

題意：給出n個數，m個詢問，問你[l,r]區間內是否為1到r-l+1的全排列。大小很容易我們通過記錄前綴和很容易求出來，但是關鍵是去重。考慮線段樹做法，我們記錄每個點的靠左最近的相同元素的位置，然後求整個區間的最大值（即最大的前驅）如果小於l,即滿足條件，輸出YES。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int MOD = 10000007;
const int INF=0x3f3f3f3f;
const int maxn=1000000+10;
int mp[maxn];
int ans[maxn],pre[maxn];
LL s[maxn];
int num[maxn],sum[maxn<<2];
int n,m;
void pushup(int rs)
{
    sum[rs]=max(sum[rs<<1],sum[rs<<1|1]);
}
void build(int rs,int l,int r)
{
    sum[rs]=0;
    if(l==r)  return ;
    int mid=(l+r)>>1;
    build(rs<<1,l,mid);
    build(rs<<1|1,mid+1,r);
}
void update(int x,int c,int l,int r,int rs)
{
    if(l==r)
    {
        sum[rs]=c;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid)  update(x,c,l,mid,rs<<1);
    else   update(x,c,mid+1,r,rs<<1|1);
    pushup(rs);
}
int query(int x,int y,int l,int r,int rs)
{
    if(l>=x&&r<=y)
        return sum[rs];
    int mid=(l+r)>>1;
    int res=0;
    if(x<=mid) res=max(res,query(x,y,l,mid,rs<<1));
    if(y>mid)  res=max(res,query(x,y,mid+1,r,rs<<1|1));
    pushup(rs);
    return res;
}
int main()
{
    int x,y;
    while(~scanf("%d%d",&n,&m))
    {
        s[0]=0;
        CLEAR(mp,0);
        CLEAR(ans,0);
        REPF(i,1,n)
        {
            scanf("%d",&num[i]);
            s[i]=s[i-1]+num[i];
            if(!mp[num[i]])
            {
                pre[i]=0;
                mp[num[i]]=i;
            }
            else
            {
                pre[i]=mp[num[i]];
                mp[num[i]]=i;
            }
            update(i,pre[i],1,n,1);
        }
        while(m--)//離線做法超時了
        {
            scanf("%d%d",&x,&y);
            LL temp=(1+y-x+1)*(y-x+1)/2;
            if(s[y]-s[x-1]==temp&&query(x,y,1,n,1)