Submission #75664229

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 2e18
#define eps 1e-9
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=2e5+5,M=4e5+5;
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,q,suf[N];
vector<int>S[N],T[N];
map<pair<int,int>,int>mp;
struct information{int Min,cnt;};
information operator + (const information &x,const information &y){
	information ret;
	ret.Min=min(x.Min,y.Min);
	if(x.Min==y.Min) ret.cnt=x.cnt+y.cnt;
	else if(ret.Min==x.Min) ret.cnt=x.cnt;
	else ret.cnt=y.cnt;
	return ret;
}
struct seg_T{
	information data[4*N];
	inline void build(int k,int l,int r){
		if(l==r){
			data[k]={suf[l],1};
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		data[k]=data[ls]+data[rs];
		return ;
	}
	inline void change(int k,int l,int r,int x,int d){
		if(l==r){
			data[k]={d,1};
			return ;
		}
		int mid=(l+r)>>1;
		if(x<=mid) change(ls,l,mid,x,d);
		else change(rs,mid+1,r,x,d);
		data[k]=data[ls]+data[rs];
		return ;
	}
	inline information query(int k,int l,int r,int x,int y){
		if(x<=l && r<=y) return data[k];
		int mid=(l+r)>>1;
		if(y<=mid) return query(ls,l,mid,x,y);
		else if(x>mid) return query(rs,mid+1,r,x,y);
		else return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
	}
}tr; 
inline bool check(int l,int r){
	if(mp[{l,r}]<1) return false;
	if(mp[{l,r}]>1) return true;
	if(l==r) return false;
	auto R=tr.query(1,1,n,l+1,r);
	if(R.Min<=r) return true;
	else return false;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int tc=1;
	while(tc--){
		cin>>n>>m;
		for(int i=1;i<=n;i++) suf[i]=inf;
		for(int i=1,l,r;i<=m;i++){
			cin>>l>>r;
			S[l].push_back(r);
			T[r].push_back(l);
			mp[{l,r}]++;
			suf[l]=min(suf[l],r);
		}
		for(int i=1;i<=n;i++){
			S[i].push_back(0);
			T[i].push_back(0);
			S[i].push_back(inf);
			T[i].push_back(inf);
			sort(S[i].begin(),S[i].end());
			sort(T[i].begin(),T[i].end());
		}
		tr.build(1,1,n);
		cin>>q;
		while(q--){
			int st,ed;
			cin>>st>>ed;
			if(check(st,ed)){
				cout<<"Yes\n";
				continue;
			}
			int pos1=upper_bound(S[st].begin(),S[st].end(),ed)-S[st].begin()-1;
			int pos2=lower_bound(T[ed].begin(),T[ed].end(),st)-T[ed].begin();
			auto r=S[st][pos1],l=T[ed][pos2];
			if(r+1<l) cout<<"No\n";
			else{
				if(l==st && r==ed){
					if(mp[{st,ed}]>=2){
						cout<<"Yes\n";
					}
					else{
						auto R=S[st][pos1-1],L=T[ed][pos2+1];
						if((R+1>=l && R!=0) || (r+1>=L && L!=inf)){
							cout<<"Yes\n";
//							cout<<l<<' '<<r<<' '<<L<<' '<<R<<"---\n";
						}
						else cout<<"No\n";
					}
				}
				else cout<<"Yes\n";
			}
		}
	} 
	
	return 0;
}

Submission Info

Judge Result