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<<1
# define rson m+1,r,rt<<1|1
# define F first
# define S second
# define N 200005
pair<int,PII> q[N];
int Max[N<<2];
int Hash[N];
void PushUp(int rt)
{
Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
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)>>1;
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=0;
if(L<=l&&R>=r)
return Max[rt];
m=(l+r)>>1;
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)>>1;
if(Hash[m]<x) l=m+1;
else r=m-1;
}
return l;
}
int main()
{
int T,i,n,x,y,num,Count,L,R;
scanf("%d",&T);
while(T--)
{
Count=0;
scanf("%d",&n);
for(i=1;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+1,Hash+Count+1);
num=1;
for(i=2;i<=Count;i++)
if(Hash[i]!=Hash[i-1])
Hash[++num]=Hash[i];
memset(Max,0,sizeof(Max));
for(i=1;i<=n;i++)
{
L=bin(1,num,q[i].S.F);
R=bin(1,num,q[i].S.S);
if(q[i].F==1) Update(L,R,1,num,1);
else
{
if(L>R) swap(L,R);
if(Query(1,L,1,num,1)>=R)
printf("YES\n");
else
printf("NO\n");
}
}
}
return 0;
}