时间限制：3 秒 / 内存限制：1024 MiB

得分： 525 分

《A - 回文数》《A - 回文数》《A - 回文数》

问题描述

在圆上有 N 个等距的点，按顺时针方向编号 1,2,…,N 。

给定 Q 个查询，形式如下；按顺序处理它们。

• 绘制连接点 Ai​ 和 Bi​ 的线段。但是，如果该线段与已绘制的线段相交，则不绘制它。

这里，保证 2Q 个整数 A1​,…,AQ​,B1​,…,BQ​ 都是不同的。

对于每个查询，回答该线段是否被绘制。

《A - 回文数》《A - 回文数》《A - 回文数》

约束条件

• 2≤N≤106
• 1≤Q≤3×105
• 1≤Ai​<Bi​≤N
• 整数 2Q 和 A1​,…,AQ​,B1​,…,BQ​ 是互不相同的。
• 所有输入值都是整数。

---

《A - 回文数》《A - 回文数》《A - 回文数》

输入

输入从标准输入中按以下格式给出：

N Q
A1​ B1​
A2​ B2​
⋮
AQ​ BQ​

《A - 回文数》《A - 回文数》《A - 回文数》

输出

输出 Q 行。在第 i 行，如果第 i 个查询中该线段被绘制，则输出 Yes ，如果未被绘制，则输出 No 。

---

《A - 回文数》《A - 回文数》《A - 回文数》

示例输入 1 复制

复制

8 3
1 5
2 7
3 4

《A - 回文数》《A - 回文数》《A - 回文数》

示例输出 1 复制

复制

Yes
No
Yes

根据查询，线段被绘制如图所示。

• 在 1 次查询中，连接点 1 和 5 的线段被绘制。
• 在 2 次查询中，连接点 2 和 7 的线段没有被绘制，因为它与 1 次查询中绘制的线段相交。
• 在 3 次查询中，连接点 3 和 4 的线段被绘制。

---

《A - 回文数》《A - 回文数》《A - 回文数》

样本输入 2 复制

复制

999999 4
123456 987654
888888 999999
1 3
2 777777

《A - 回文数》《A - 回文数》《A - 回文数》

样本输出 2 复制

复制

Yes
No
Yes
No

思路

用线段树维护最大最小。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long n,q,a,b,lk=0;
long long tr[4000006],tr2[4000006];
void ci(long long a1,long long l,long long r,long long x,long long y){
	if(l==r&&l==x){
		//cout<<l<<endl;
		tr[a1]=max(tr[a1],y);
		return ;
	}
	long long mid=(l+r)/2;
	if(x<=mid){
		ci(a1*2,l,mid,x,y);
	}
	else{
		ci(a1*2+1,mid+1,r,x,y);
	}
	tr[a1]=max(tr[a1*2],tr[a1*2+1]);
	return ;
}
long long co(long long a1,long long l,long long r,long long x,long long y){
	if(l>=x&&r<=y){
		return tr[a1];
	}
	long long mid=(l+r)/2,op=0;
	if(x<=mid){
		op=max(op,co(a1*2,l,mid,x,y));
	}
	if(y>=mid+1){
		op=max(op,co(a1*2+1,mid+1,r,x,y));
	}
	//tr[a1]=max(tr[a1*2],tr[a1*2+1]);
	return op;
}
void ci2(long long a1,long long l,long long r,long long x,long long y){
	if(l==r&&l==x){
		tr2[a1]=min(tr2[a1],y);
		return ;
	}
	long long mid=(l+r)/2;
	if(x<=mid){
		ci2(a1*2,l,mid,x,y);
	}
	else{
		ci2(a1*2+1,mid+1,r,x,y);
	}
	tr2[a1]=min(tr2[a1*2],tr2[a1*2+1]);
	return ;
}
long long co2(long long a1,long long l,long long r,long long x,long long y){
	if(l>=x&&r<=y){
		return tr2[a1];
	}
	long long mid=(l+r)/2,op=1e18+7;
	if(x<=mid){
		op=min(op,co2(a1*2,l,mid,x,y));
	}
	if(y>=mid+1){
		op=min(op,co2(a1*2+1,mid+1,r,x,y));
	}
	//tr2[a1]=min(tr2[a1*2],tr2[a1*2+1]);
	return op;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=4*n;i++){
		tr2[i]=1e18+7;
	} 
	for(int i=1;i<=q;i++){
		cin>>a>>b;
		if(b<=a){
			swap(a,b);
		}
		//cout<<co(1,1,n,a,b)<<" "<<co2(1,1,n,a,b)<<endl;
		if(co(1,1,n,a,b)<=b&&co2(1,1,n,a,b)>=a){
			lk++;
			ci(1,1,n,a,b);
			ci2(1,1,n,b,a);
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
	//cout<<lk<<endl;
	return 0;
}