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

yedalong · 2025-10-07 08:54:16 · 题解

线段树好题。

跟二分配在一起有点阴间。。。

Solution

注意到一个重要性质：每次添加 l 到 r 的线段添加多条和添加一条最长的意义是一样的，读者易证。

因此我们可以每次二分寻找 l 到 r 区间中最长的线段左右两个端点，直接用线段树模拟即可。

实现上有许多细节，具体可以看我的代码。

AC code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=5e5+5;
int n,q,opt,l,r,x,p[MAXN],ll[MAXN],rr[MAXN],qzh[MAXN],tree[4*MAXN],a[MAXN],tag[4*MAXN];
inline int lc(int x){return x<<1;}
inline int rc(int x){return x<<1|1;}
inline void push_up(int now){tree[now]=min(tree[lc(now)],tree[rc(now)]);}
inline void f(int now,int k){tree[now]+=k,tag[now]+=k;}
inline void push_down(int now){
    f(lc(now),tag[now]);
    f(rc(now),tag[now]);
    tag[now]=0;
}
inline void build(int l,int r,int now){
    if(l==r){
        tree[now]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,lc(now));
    build(mid+1,r,rc(now));
    push_up(now);
}
inline void update(int l,int r,int now,int nl,int nr,int k){
    if(l>nr||r<nl) return;
    if(l>=nl&&r<=nr){
        f(now,k);
        return;
    }
    push_down(now);
    int mid=l+r>>1;
    update(l,mid,lc(now),nl,nr,k);
    update(mid+1,r,rc(now),nl,nr,k);
    push_up(now);
}
int find1(int x){
    int l=x,r=n,res=1e9;
    while(l<=r){
        int mid=l+r>>1;
        if(qzh[mid]!=qzh[x-1]) r=mid-1,res=mid;
        else l=mid+1;
    }
    return res;
}
int find2(int x){
    int l=1,r=x,res=1e9;
    while(l<=r){
        int mid=l+r>>1;
        if(qzh[mid-1]!=qzh[x]) l=mid+1,res=mid;
        else r=mid-1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i<=n;i++) cin>>p[i];
    for(int i = 1;i<=n;i++) cin>>a[i],qzh[i]=qzh[i-1]+a[i];//qzh 用于判断 l 和 r 之间是否有 1，判断为：qzh[l-1]!=qzh[r] 
    build(1,n,1);
    if(tree[1]) cout<<"Yes\n";
    else cout<<"No\n";
    for(int i = 1;i<=q;i++){
        cin>>opt;
        if(opt==1){
            cin>>l>>r;
            int tmpl=lower_bound(p+1,p+1+n,l)-p,tmpr=upper_bound(p+1,p+1+n,r)-p-1;
            //tmpl 表示 l 右边的第一个特殊整点，tmpr 表示 r 左边的第一个特殊整点
            bool flag=1;
            if(p[tmpl]>r||p[tmpr]<l){//判断越界情况 
                ll[i]=-1,rr[i]=-1;
                flag=0;
            }
            ll[i]=find1(tmpl),rr[i]=find2(tmpr);//寻找 tmpl 和 tmpr 之间最大的黑色的区间 
            if(ll[i]>tmpr||rr[i]<tmpl||ll[i]==1e9||rr[i]==1e9||ll[i]>rr[i]){//判断不合法情况 
                ll[i]=-1,rr[i]=-1;
                flag=0;
            }
            if(flag) update(1,n,1,ll[i],rr[i],1);
        }
        else{
            cin>>x;
            if(ll[x]!=1e9) update(1,n,1,ll[x],rr[x],-1);
        }
        if(tree[1]) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}