自动搬运

查看原文

来自洛谷，原作者为

	maxiaomeng 下留有没也么什，懒很伙家个这

搬运于2025-08-24 22:39:22，当前版本为作者最后更新于2025-08-19 15:39:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先发现一次添加操作虽然添加了很多线段，但其中只有最长的左右端点都是黑点的线段有用，因为其它的线段都被包含在最长的里面，不如最长的优。

然后发现染色操作中，不必考虑被染黑的白点会带来更多可染色线段。

理由如下：假如存在线段 $CD$ 左右端点有白点，但线段 $AB$ 染色后线段 $CD$ 端点均为黑点，则有两种情况：

• $AB$ 包含 $CD$，此时 $CD$ 不如 $AB$ 优。
• $AB$ 与 $CD$ 有交，但不包含 $CD$。不妨设 $D$ 在 $AB$ 上，则选 $CA$ 和 $CB$ 一定不劣于 $CD$。

因此直接覆盖所有最长的左右端点都是黑点的线段，判断是否所有白点都被染色即可。有添加和撤销操作，可用线段树的区间加减实现，查询直接查全局最小值是否大于等于 $0$（黑点初始设为无穷大）。

求最长的左右端点都是黑点的线段，可用二分找到大于等于左端点的最左边黑点和小于等于右端点的最右边黑点。

#include<bits/stdc++.h>
#define int long long
#define __builtin_popcount __builtin_popcountll
#define endl '\n'
using namespace std;
const int N=500010;
int n,m,a[N],w[N],pc;
struct node{
	int l,r,x,y,t;
}tree[N<<2];
pair<int,int>p[N],z[N];
inline void spread(int x){
	tree[x<<1].t+=tree[x].t;
	tree[x<<1|1].t+=tree[x].t;
	tree[x<<1].x+=tree[x].t*(tree[x<<1].r-tree[x<<1].l+1);
	tree[x<<1|1].x+=tree[x].t*(tree[x<<1|1].r-tree[x<<1|1].l+1);
	tree[x<<1].y+=tree[x].t;
	tree[x<<1|1].y+=tree[x].t;
	tree[x].t=0;
}
inline void pushup(int x){
	tree[x].x=tree[x<<1].x+tree[x<<1|1].x;
	tree[x].y=min(tree[x<<1].y,tree[x<<1|1].y);
}
void build(int x,int l,int r){
	tree[x].l=l;
	tree[x].r=r;
	if(l==r){
		tree[x].x=tree[x].y=a[l];
		return;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void add(int x,int l,int r,int v){
	int L=tree[x].l,R=tree[x].r;
	if(l>R||r<L)return;
	if(l<=L&&R<=r){
		tree[x].t+=v;
		tree[x].x+=v*(R-L+1);
		tree[x].y+=v;
		return;
	}
	spread(x);
	add(x<<1,l,r,v);
	add(x<<1|1,l,r,v);
	pushup(x);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]*=0x3f3f3f3f;
		if(a[i])p[++pc]={w[i],i};
	}
	p[0]={-(int)(0x3f3f3f3f),0};
	p[pc+1]={0x3f3f3f3f,n+1};
	a[0]=a[n+1]=0x3f3f3f3f;
	build(1,0,n+1);
	if(tree[1].y)cout<<"Yes\n";
	else cout<<"No\n";
	for(int i=1;i<=m;i++){
		int o,x,y;
		cin>>o>>x;
		if(o&1){
			cin>>y;
			z[i]={x,y};
			int l=lower_bound(p,p+pc+2,make_pair(x,0ll))->second,r=(upper_bound(p,p+pc+2,make_pair(y,0x3f3f3f3fll))-1)->second;
			if(l<=r)add(1,l,r,1);
		}else{
			auto [X,Y]=z[x];
			int l=lower_bound(p,p+pc+2,make_pair(X,0ll))->second,r=(upper_bound(p,p+pc+2,make_pair(Y,0x3f3f3f3fll))-1)->second;
			if(l<=r)add(1,l,r,-1);
		}
		if(tree[1].y)cout<<"Yes\n";
		else cout<<"No\n";
	}
    return 0;
}