自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:08:11，当前版本为作者最后更新于2025-01-12 12:19:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

给个 $O((n+q) \log^2 n)$ 的做法，不需要任何思考，而且运行时间只是单 $\log$ 的两倍。

考虑扫描线，对于 $l=n,n-1,\cdots,1$，维护每个 $r \ge l$，用 $[l,r]$ 内包含的连续段能覆盖的最长的连续后缀长度，设为 $a_r$。我们只需要询问 $a_r=l$ 是否成立。

现在考虑一个 $[l,x]$ 的新线段。对于 $r \ge x$ 且 $a_r \le x+1$，都可以有 $a_r \leftarrow l$。

发现这个形式和区间取 $\min$ 非常像，所以可以直接上线段树势能，复杂度 $O(n \log^2 n)$。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int MAXN=5e5+10;
int n,m,q,ans[MAXN],tag[MAXN<<2];
vector<int> seg[MAXN];
vector<pair<int,int>> qr[MAXN];
struct INFO {int mn,smn;}t[MAXN<<2];
inline int calc(const int a,const int b,const int c,const int d) {if(a==b) return min(c,d);if(a<b) return min(b,c);return min(a,d);	}
INFO operator +(INFO A,INFO B) {return {min(A.mn,B.mn),calc(A.mn,B.mn,A.smn,B.smn)};}
void assign(int k,int tg) {
	tag[k]=tg,t[k].mn=tg;
	return ;
}
void push_down(int k,int l,int r) {
	if(tag[k]!=-1) {
		int flg1=0,flg2=0;
		if(t[lson].mn<=t[rson].mn) flg1=1;
		if(t[rson].mn<=t[lson].mn) flg2=1;
		if(flg1) assign(lson,tag[k]);
		if(flg2) assign(rson,tag[k]);
	}
	return tag[k]=-1,void();
}
void update(int k,int l,int r,int x,int y,int v,int nv) {
	if(t[k].mn>v) return ;
	if(x<=l&&r<=y) {
		if(t[k].smn>v) return assign(k,nv),void();
		push_down(k,l,r);
		update(lson,l,mid,x,y,v,nv);
		update(rson,mid+1,r,x,y,v,nv);
		return t[k]=t[lson]+t[rson],void();	
	}
	push_down(k,l,r);
	if(x<=mid) update(lson,l,mid,x,y,v,nv);
	if(y>mid) update(rson,mid+1,r,x,y,v,nv);
	return t[k]=t[lson]+t[rson],void();
}
void build(int k,int l,int r) {
	tag[k]=-1;
	if(l==r) return t[k]={l+1,n+100},void();
	build(lson,l,mid),build(rson,mid+1,r);
	return t[k]=t[lson]+t[rson],void();	
}
int query(int k,int l,int r,int pos) {
	if(l==r) return t[k].mn;
	push_down(k,l,r);
	if(pos<=mid) return query(lson,l,mid,pos);
	return query(rson,mid+1,r,pos);	
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	ffor(i,1,m) {
		int l,r;
		cin>>l>>r,seg[l].push_back(r);	
	}
	ffor(i,1,q) {
		int s,e;
		cin>>s>>e,qr[s].push_back({e,i});	
	}
	build(1,1,n);
	roff(i,n,1) {
		for(auto id:seg[i]) update(1,1,n,id,n,id+1,i);
		for(auto pr:qr[i]) if(query(1,1,n,pr.first)==i) ans[pr.second]=1;
	}
	ffor(i,1,q) if(ans[i]) cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}