专栏文章

题解：CF1998E2 Eliminating Balls With Merging (Hard Version)

LLiaoYF1
CF1998E2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mini68g7
此快照首次捕获于
2025/12/02 02:48
3 个月前
此快照最后确认于
2025/12/02 02:48
3 个月前
查看原文

做法

一种不太相同的做法。下文的“吃掉”指原题面中的合并。
首先考虑我们怎么判断 ii 是否能吃掉所有的。定义 nxtinxt_i 为使得 ∑i+1nxtiai≥i\sum_{i+1}^{nxt_i} a_i\geq i 成立的最小的数。假设 xx 在 ii 左边，那么 ii 可以吃掉 xx，当且仅当 ii 吃掉了 x+1x+1，且吃掉了 nxtxnxt_x。xx 在 ii 右边的情况同理。我们将每个这种依赖关系连一条边，会形成一个有向图，如果图中无环则 ii 可以吃掉所有的。
考虑研究环的形态。如下图，环一定形如两个相交但是不包含的区间，且靠前的区间方向向右，靠后的区间方向向左，此时选取相交的部分中的点（不包含边界），都会产生环。故相交的部分都不合法。
考虑如何求出 11 到 rr 的答案。每次前缀向右扩展一位时，加入所有右端点为 rr 的区间。对于每个向左的区间 [l,r][l,r]，查找所有左端点比它小的向右的区间中，右端点最大是多少，线段树维护单点修改，区间 min。然后将中间全部标记为不合法。再开一个线段树维护区间推平、区间和即可。注意处理不可能被吃掉的点。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define pii pair<ll,ll>
#define fi first
#define se second
#define i128 __int128
#define ALL(x) x.begin(),x.end()
#define popcount(x) __builtin_popcountll(x)
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
const int INF=1e18;
const int N=200005;
const int MOD1=1e9+7,MOD2=998244353;
const int MOD=MOD1;
int n,a[N];
int q;
int s[N];
int pre[N],nxt[N];
int f[N];
int ans=0;
struct segtree1{
    //区间推平 区间求和
    int tr[4*N];
    int tag[4*N];
    void pushup(int p){
        tr[p]=tr[p*2]+tr[p*2+1];
    }
    void pushdown(int p){
        if(tag[p]){
            tr[p*2]=0;
            tag[p*2]=1;
            tr[p*2+1]=0;
            tag[p*2+1]=1;
            tag[p]=0;
        }
    }
    void build(int p,int l,int r){
        tag[p]=0;
        if(l==r){
            tr[p]=1;
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int L,int R){
        if(L>R)return;
        if(l>=L&&r<=R){
            tr[p]=0;
            tag[p]=1;
            return;
        }
        pushdown(p);
        int mid=(l+r)/2;
        if(mid>=L)modify(p*2,l,mid,L,R);
        if(mid<R)modify(p*2+1,mid+1,r,L,R);
        pushup(p);
    }
    int query(int p,int l,int r,int L,int R){
        if(L>R)return 0;
        if(l>=L&&r<=R){
            return tr[p];
        }
        pushdown(p);
        int mid=(l+r)/2,res=0;
        if(mid>=L)res+=query(p*2,l,mid,L,R);
        if(mid<R)res+=query(p*2+1,mid+1,r,L,R);
        return res;
    }
}T1;
struct segtree2{
    //单点修 区间max
    int tr[4*N];
    void pushup(int p){
        tr[p]=max(tr[p*2],tr[p*2+1]);
    }
    void build(int p,int l,int r){
        if(l==r){
            tr[p]=0;
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
    void modify(int p,int l,int r,int x,int c){
        if(l==r){
            tr[p]=max(tr[p],c);
            return;
        }
        int mid=(l+r)/2;
        if(mid>=x)modify(p*2,l,mid,x,c);
        else modify(p*2+1,mid+1,r,x,c);
        pushup(p);
    }
    int query(int p,int l,int r,int L,int R){
        if(l>=L&&r<=R){
            return tr[p];
        }
        int mid=(l+r)/2,res=0;
        if(mid>=L)res=max(res,query(p*2,l,mid,L,R));
        if(mid<R)res=max(res,query(p*2+1,mid+1,r,L,R));
        return res;
    }
}T2;
void init(){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        //pre:连到i的点
        int l=1,r=i-1,res=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(s[i-1]-s[mid-1]>=a[i]){
                res=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        pre[i]=res;
    }
    for(int i=n;i>=1;i--){
        int l=i+1,r=n,res=n+1;
        while(l<=r){
            int mid=(l+r)/2;
            if(s[mid]-s[i]>=a[i]){
                res=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        nxt[i]=res;
    }
    // for(int i=1;i<=n;i++){
    //     debug(i,pre[i],nxt[i]);
    // }
}
vector<pii> vec1[N],vec2[N];
int sufmn[N];//后缀min
void solve_(){
    int x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        vec1[i].clear();
        vec2[i].clear();
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    for(int i=1;i<=n+1;i++){
        sufmn[i]=INF;
    }
    for(int i=1;i<=n;i++){
        sufmn[nxt[i]]=min(sufmn[nxt[i]],i);
    }
    for(int i=n;i>=1;i--){
        sufmn[i]=min(sufmn[i],sufmn[i+1]);
    }
    T1.build(1,1,n);
    T2.build(1,1,n);
    for(int i=1;i<=n;i++){
        if(pre[i]!=0){
            vec1[i].push_back({pre[i],i});
        }
        if(nxt[i]!=n+1){
            vec2[nxt[i]].push_back({i,nxt[i]});
        }
    }
    int ql=1;
    for(int i=1;i<=n;i++){
        //加入区间
        for(auto [x,y]:vec1[i]){
            T2.modify(1,1,n,x,y);
        }
        for(auto [x,y]:vec2[i]){
            int t=T2.query(1,1,n,1,x);
            //debug(t,x);
            if(t>=x){
                T1.modify(1,1,n,x+1,t-1);
            }
        }
        if(pre[i]==0){
            ql=max(ql,i);
        }
        int qr=min(i,sufmn[i+1]);
        //if(i==7)debug(ql,qr);
        cout<<T1.query(1,1,n,ql,qr)<<" ";
    }
    cout<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase,multitest=1;
    if(multitest)cin>>testcase;
    else testcase=1;
    while(testcase--){
        solve_();

    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...