P11536 [NOISG 2023 Finals] Curtains

首先想到离线，将询问按 $e$ 排序。

处理到某个 $e_i$ 时只加入 $r_j \le e_i$ 的区间。

能将 $[s_i,e_i]$ 恰好覆盖的充要条件是区间内每个数都能被某个 $[l_j,r_j]$ 覆盖，且其中所有 $l_j$ 满足 $l_j \ge s_i$。

令 $f_x = \max \limits _{l_j \le x \le r_j \le e_i} \{ l_j \}$，则当且仅当 $\min \limits _{s_i \le x \le e_i} {f_x} = s_i$ 时，能将 $[s_i,e_i]$ 恰好覆盖。

加入区间 $[l_j,r_j]$ 时，将 $[l_j,r_j]$ 中的所有 $f$ 与 $l_j$ 取最大值。用线段树维护。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
struct node{
	int l,r,lz,Min;
}T[N<<2];
struct Q{
	int s,id;
};
void push_up(int p){
	T[p].Min=min(T[p<<1].Min,T[p<<1|1].Min);
}
void build(int p,int l,int r){
	T[p].l=l,T[p].r=r;
	if(l==r)return;
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void push_down(int p){
	T[p<<1].lz=max(T[p<<1].lz,T[p].lz);
	T[p<<1|1].lz=max(T[p<<1|1].lz,T[p].lz);
	T[p<<1].Min=max(T[p<<1].Min,T[p].lz);
	T[p<<1|1].Min=max(T[p<<1|1].Min,T[p].lz);
	T[p].lz=0;
}
void update(int p,int l,int r,int v){
	if(T[p].r<l||T[p].l>r)return;
	if(l<=T[p].l&&T[p].r<=r){
		T[p].Min=max(T[p].Min,v);
		T[p].lz=max(T[p].lz,v);
		return ;
	}
	push_down(p);
	update(p<<1,l,r,v);
	update(p<<1|1,l,r,v);
	push_up(p);
}
int query(int p,int l,int r){
	if(T[p].r<l||T[p].l>r)return 0x3f3f3f3f;
	if(l<=T[p].l&&T[p].r<=r)return T[p].Min;
	return min(query(p<<1,l,r),query(p<<1|1,l,r));
}
int n,m,q;
bool ans[N];
vector<int>L[N];
vector<Q>qry[N];
int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int l,r;m--;){
		scanf("%d%d",&l,&r);
		L[r].push_back(l);
	}
	for(int s,e,i=1;i<=q;i++){
		scanf("%d%d",&s,&e);
		qry[e].push_back(Q{s,i});
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		for(int l:L[i])update(1,l,i,l);
		for(Q x:qry[i])ans[x.id]=(query(1,x.s,i)==x.s);
	}
	for(int i=1;i<=q;i++)puts(ans[i]?"YES":"NO");
	return 0;
}