P4497 [WC2011]拼点游戏

· · 题解

P4497 [WC2011]拼点游戏

在我的 cnblogs 中查看

数据结构大杂烩 + 阿巴细节题。

调了三个小时。

首先考虑第一小问的答案。

注意到点数的计算方式是先负后正的形式，不妨看做选出 2k 个数 p_1,p_2,\cdots,p_{2k}，从小到大排序后计算 \sum u_{p_{2i}-p_{2i-1}}。再根据题目的区间修改操作，不难想到使用差分：

设 d_i=u_i-u_{i-1}，舍去 d_1 后得到一个长度为 n-1 的序列 d_2,d_3,\cdots,d_n。不难发现，选择一段连续的 d 并求和就相当于选择两个端点对应的 u 求差，即 d_l+d_{l+1}+\cdots+d_r=u_r-u_{l-1}。可以证明任何一种 d 中的选数方式都对应了 u 中的一种选数方式，故题目转化为在 d 中选出若干不相邻子段，求选出的数的和的最大值。

因此，为了让得分最大，我们只选取所有大于 0 的 d 即可，即 \sum_{i=2}^n\max(0,d_i)。

不妨设最终选取的 d 中的数的区间为 [l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]。考虑小 Y（不是小 W）的修改操作的本质：选取两个编号相邻（不是在 d 中相邻）的区间 [a,b],[c,d]\ (a\leq b<c\leq d,b+1<c)，将 b,c 分别换成任意 z_1,z_2\in [b,c] 满足 z_1+1<z_2。

为了让减小的得分最多且最终两区间端点不相邻，又因为 (b,c) 中全是非正数，故留下最大的那一个数即可。得分的减少量即为区间 (b,c) 的和减去它的最大值，即 \left(\sum_{i=b+1}^{c-1}d_i\right)-\left(\max_{i=b+1}^{c-1}d_i\right)。

例如 positive integer | -6 | -5 | -7 | -8 | positive integers，我们就可以将 b\gets b+1，c\gets c-2，此时得分减小 6+7+8=21，是最优的。

如果我们选了 m 个这样的区间，那么它们之间就有 m-1 个空隙可以用来减小分数。对于这 m-1 个空隙，分别计算它的得分最大减少量并丢到平衡树 or 动态开点线段树上。每个节点记录落在该区间的数的个数以及它们的和，则最终可以通过线段树上二分（原理类似主席树求区间第 k 小）求出答案。

同时，对于操作 1，我们通过差分将其转化为了两次单点修改，而单点修改对于选择的区间的影响是 \mathcal{O}(1) 的，于是我们可以暴力 \log n 重新计算被影响的区间的答案即可。因为我们只关心 “被选择区间” 之间形成的 “空隙区间” 的信息，前者只需求和，所以记录后者即可。具体地，用线段树维护区间最大值与区间和，并用 set 维护 “空隙区间” 的端点信息，方便修改。

时间复杂度为 Tn\log n\sim Tn\log w，其中 w 为值域。

当然，说起来轻巧，实现却并不简单。有亿些细节需要注意：都是踩过的坑啊。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mem(x,v) memset(x,v,sizeof(x))
#define pii pair <int,int>
#define fi first
#define se second

const int N=1e5+5;
const ll W=1ll<<31;

ll n,q,ans,u[N],d[N];

// SegTree 1
ll mval[N<<2];
void build(int l,int r,int x){
    if(l==r)return mval[x]=d[l],void();
    int m=l+r>>1;
    build(l,m,x<<1),build(m+1,r,x<<1|1);
    mval[x]=max(mval[x<<1],mval[x<<1|1]);
}
void modify(int l,int r,int p,int x,ll v){
    if(l==r)return mval[x]=v,void();
    int m=l+r>>1;
    if(p<=m)modify(l,m,p,x<<1,v);
    else modify(m+1,r,p,x<<1|1,v);
    mval[x]=max(mval[x<<1],mval[x<<1|1]);
}
ll query(int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr)return mval[x];
    ll m=l+r>>1,ans=-W;
    if(ql<=m)ans=max(ans,query(l,m,ql,qr,x<<1));
    if(m<qr)ans=max(ans,query(m+1,r,ql,qr,x<<1|1));
    return ans;
}

// BIT
ll c[N];
void add(int x,ll v){while(x<=n)c[x]+=v,x+=x&-x;}
ll query(int x){ll s=0; while(x)s+=c[x],x-=x&-x; return s;}
ll query(int l,int r){return query(r)-query(l-1);}

// end points
set <pii> s;
ll cont[N];

// SegTree 2
ll R,node,ls[N<<6],rs[N<<6],val[N<<6],sum[N<<6];
void insert(ll l,ll r,ll p,ll &x,bool tp){
    if(!x)x=++node;
    if(tp)sum[x]++,val[x]+=p-W;
    else sum[x]--,val[x]-=p-W;
    if(l==r)return;
    ll m=l+r>>1;
    if(p<=m)insert(l,m,p,ls[x],tp);
    else insert(m+1,r,p,rs[x],tp);
}
ll query(ll l,ll r,ll k,ll x){
    if(!x)return -W;
    if(l==r)return k+val[x]<=0?((k-1)/(W-l)+1):-W;
    ll m=l+r>>1;
    if(k+val[ls[x]]<=0)return query(l,m,k,ls[x]);
    return sum[ls[x]]+query(m+1,r,k+val[ls[x]],rs[x]);
}

void clear(pii x){
    if(x.fi==1||x.se==n-1)return;
    insert(1,W,cont[x.fi]+W,R,0),cont[x.fi]=0;
}
void update(int l,int r){
    if(l==1||r==n-1)return;
    cont[l]=query(l,r)-query(1,n,l,r,1);
    insert(1,W,cont[l]+W,R,1);
}

// update changes
void change(int pos,ll &val,ll add){
    auto it=s.upper_bound({pos,N});

    // update end points and contribution
    if(val<=0&&val+add>0){
        ans+=val+add;
        pii x=*--it; clear(x),s.erase(x);
        if(x.fi==x.se)return val+=add,void();
        else if(x.fi==pos)s.insert({++x.fi,x.se}),update(x.fi,x.se);
        else if(pos==x.se)s.insert({x.fi,--x.se}),update(x.fi,x.se);
        else{
            s.erase(x);
            s.insert({x.fi,pos-1}),update(x.fi,pos-1);
            s.insert({pos+1,x.se}),update(pos+1,x.se);
        }
    }
    else if(val>0&&val+add<=0){
        ans-=val;
        pii x={pos,pos};
        if(it!=s.begin()){
            pii tmp=*(--it); it++;
            if(tmp.se==pos-1)clear(tmp),s.erase(tmp),x.fi=tmp.fi;
        } if(it!=s.end()){
            pii tmp=*it;
            if(tmp.fi==pos+1)clear(tmp),s.erase(tmp),x.se=tmp.se;
        } s.insert(x),update(x.fi,x.se);
    } else if(val<=0&&val+add<=0)it--,clear(*it),update((*it).fi,(*it).se);
    else ans+=add; val+=add;
}

void solve(){
    // empty
    mem(c,0),mem(cont,0),s.clear(),ans=0;
    R=node,mem(ls,0),mem(rs,0),mem(val,0),mem(sum,0);

    // read
    cin>>n>>q>>u[0];
    for(int i=1;i<n;i++){
        cin>>u[i],d[i]=u[i]-u[i-1];
        if(d[i]>0)ans+=d[i];
        add(i,d[i]);
    } build(1,n,1);

    // find end points [l,r)
    for(int i=1,pre=1;i<n;i++){
        if(d[i]<=0&&d[i-1]>0)pre=i;
        if(d[i]>0&&d[i-1]<=0){
            s.insert({pre,i-1});
            if(pre!=1)update(pre,i-1);
        } if(i==n-1&&d[i]<=0)s.insert({pre,n-1});
    }

    // answer all the queries
    for(int i=1;i<=q;i++){
        int op; cin>>op;
        if(op==0){
            ll l,r,c; cin>>l>>r>>c,l--,r--;

            // modify SegTree 1 & BIT then update answer
            if(l)add(l,c),modify(1,n,l,1,d[l]+c),change(l,d[l],c);
            if(r+1<n)add(r+1,-c),modify(1,n,r+1,1,d[r+1]-c),change(r+1,d[r+1],-c);
        }
        else cout<<ans<<" "<<(ans?max(-1ll,query(1,W,ans,R)):0)<<endl;
    }
}
int main(){
    int T; cin>>T;
    while(T--)solve();
    return 0;
}