BUAA 724 晴天小猪的神题(RMQ线段树)

BUAA 724 晴天小猪的神题

题意:中文题,略

题目链接:http://acm.buaa.edu.cn/problem/724/

思路:对于询问x,y是否在同一区间,可以转换成有没有存在一个区间它的左端点小于等于x,右端点大于等于y

即小于等于x的所有区间的右端点的最大值是否大于y!这就转换成了区间最值问题,可以用线段树动态维护左端点即可

(x,y太大，可先离散化)

# include<cstdio>

# include<cstring>

# include<map>

# include<algorithm>

using namespace std;

typedef pair<int,int> PII;

# define lson l,m,rt<<

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

# define F first

# define S second

# define N

pair<int,PII> q[N];

int Max[N<<];

int Hash[N];

void PushUp(int rt)

{

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

}

void Update(int pos,int x,int l,int r,int rt)

{

    int m;

    if(l==r)

    {

        Max[rt]=max(Max[rt],x);

        return;

    }

    m=(l+r)>>;

    if(pos<=m) Update(pos,x,lson);

    else Update(pos,x,rson);

    PushUp(rt);

}

//查询[L,R]内的最大值

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

{

    int m,ans=;

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

        return Max[rt];

    m=(l+r)>>;

    if(L<=m) ans=max(ans,Query(L,R,lson));

    if(R>m) ans=max(ans,Query(L,R,rson));

    return ans;

}

int bin(int l,int r,int x)

{

    int m;

    while(l<=r)

    {

        m=(l+r)>>;

        if(Hash[m]<x) l=m+;

        else r=m-;

    }

    return l;

}

int main()

{

    int T,i,n,x,y,num,Count,L,R;

    scanf("%d",&T);

    while(T--)

    {

        Count=;

        scanf("%d",&n);

        for(i=;i<=n;i++)

        {

            scanf("%d%d%d",&q[i].F,&q[i].S.F,&q[i].S.S);

            Hash[++Count]=q[i].S.F;

            Hash[++Count]=q[i].S.S;

        }

        sort(Hash+,Hash+Count+);

        num=;

        for(i=;i<=Count;i++)

            if(Hash[i]!=Hash[i-])

                Hash[++num]=Hash[i];

        memset(Max,,sizeof(Max));

        for(i=;i<=n;i++)

        {

            L=bin(,num,q[i].S.F);

            R=bin(,num,q[i].S.S);

            if(q[i].F==) Update(L,R,,num,);

            else

            {

                if(L>R) swap(L,R);

                if(Query(,L,,num,)>=R)

                    printf("YES\n");

                else

                    printf("NO\n");

            }

        }

    }

    return ;

}

BUAA 724

BUAA 724 晴天小猪的神题(RMQ线段树)的相关教程结束。