题解：P8473 [Aya Round 1 H] 破碎的历史

· · 题解

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

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

理由如下：假如存在线段 CD 左右端点有白点，但线段 AB 染色后线段 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;
}