[C++知识库]道路维修 题解

道路维修 题解

输入样例：
4
5 3 3
2 4 5
3 1 2
5 2 3
4
2 3 2 2
1 4 2 3
2 5 2 4
3 5 1 5
输出样例：
Yes
No
Yes
No
代码如下（示例）：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
	int l,r;
	int mn,lazy;
}tr[N<<2];
void pushup(int u){
	tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
}
void pushdown(int u){
	if(tr[u].lazy){
		tr[u<<1].mn=tr[u<<1].lazy=tr[u].lazy;
		tr[u<<1|1].mn=tr[u<<1|1].lazy=tr[u].lazy;
		tr[u].lazy=0;
	}
}
void build(int u,int l,int r){
	tr[u]={l,r};
	if(l==r) return ;
	int mid=l+r>>1;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}
void update(int u,int l,int r,int v){
	if(tr[u].l>=l&&tr[u].r<=r){
		tr[u].mn=tr[u].lazy=v;
		return ;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) update(u<<1,l,r,v);
	if(r>mid) update(u<<1|1,l,r,v);
	pushup(u);
}
int ask(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mn;
	int mid=tr[u].l+tr[u].r>>1;
	pushdown(u);
	int res=1e9;
	if(l<=mid) res=min(res,ask(u<<1,l,r));
	if(r>mid) res=min(res,ask(u<<1|1,l,r));
	return res;
}
struct Query{
	int l,r,x,y,pos;
}q[N]; 
bool cmp1(Query a,Query b){
	return a.r<b.r;
}

struct Node{
	int v,l,r;
}p[N];
bool cmp2(Node a,Node b){
	return a.v<b.v;
}
int ans[N];
int main(){
	int n,m;
	scanf("%d",&n);
	build(1,1,N);
	for(int i=1;i<=n;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		p[i]={a,b,c};
	}
	sort(p+1,p+1+n,cmp2);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int l,r,a,b;
		scanf("%d%d%d%d",&l,&r,&a,&b);
		q[i]={l,r,a,b,i};
	}
	sort(q+1,q+1+m,cmp1);
	for(int i=1,j=1;i<=m;i++){
		while(j<=n&&q[i].r>=p[j].v){
			update(1,p[j].l,p[j].r,p[j].v);
			j++;
		}
		int tt=ask(1,q[i].x,q[i].y);
		if(tt<q[i].l) ans[q[i].pos]=-1;
	}
	for(int i=1,j=1;i<=m;i++){
		if(ans[i]==-1) puts("No");
		else puts("Yes");
	}
	return 0;
}