P9168 [省选联考 2023] 人员调度

_jimmywang_ · 2023-04-27 22:38:20 · 题解

Extracted from 联合省选记录

• P9168 [省选联考 2023] 人员调度

我和贪心势不两立！

删除操作很恶心，先不管。我们先来看不带删除怎么做。

定义一个员工为 (u,x) 表示初始部门是 u，能力值是 x。

考虑对每个点 u 维护一个员工集合 S_u，满足 \forall u，S_u是初始部门是 u 的员工集合的子集。并且，将所有员工 (U,x) 与其初始部门 U 的子树中所有的点连边，形成一张员工到点的二分图，满足该二分图存在员工的完美匹配。

这样就满足了存在一种题目中的分配（下放）方式，使得所有点上的员工数 \leq 1。

相当于不考虑一个方案中没有贡献的点，而根据最优性，题目的一个最优方案一定能和一组 S_u 一一对应。

设 size_u 是 u 的子树大小。

根据 Hall 定理，一个方案满足条件的充要条件是 \forall u,\sum_{v\in u\text{ 的子树 }}|S_v|\leq size_u，即子树内保留的员工个数不超过子树大小。

证明感性理解，大概是每个员工子集都拆成不相交子树，然后在一个子树内限制尽量紧，于是把子树内所有的员工算上也要满足。具体不证了（要的话评论加一下）。

记 left_u=size_u-\sum_{v\in u \text{ 的子树 }}|S_v|，即 u 的子树内还能放多少个员工。于是方案合法等价于 \forall u,left_u\geq 0。

考虑加入一个员工 (u,x) 的影响。

如果直接加入这个员工合法，那么由于加入它会使 u 及其祖先子树中的空位都减少 1，所以要满足 u 及其祖先的 left 均不为 0。此时直接在 u 加入这个员工是合法的。那么就果断加入。

但是如果 u 及其祖先的 left 存在一个点为 0 呢？

那我们如果要加入这个员工，必定要踢掉一个。我们找到 u 及其祖先中，深度最深且 left=0 的点，记为 v。由上面的充要条件得，这个时候必须在 v 的子树内踢掉一个。

于是我们查询 v 的子树内保留的员工的最小值。若用现在这个员工替换他更优，那么我们就踢掉一个最小值，并加入当前员工 (u,x)。

至此，不带删的东西做完了。

至于具体实现，我们树剖维护 left，操作有链上 \pm 1 和查询链上最小值（及其最深的位置）；而对于员工集合 S_u，我们给每个节点开一个 multiset，记录员工的能力值集合。即 w_u 为 u 的 multiset 中的最小值（就是员工最小能力值），查询子树内员工最小值即为查询区间内 w 的最小值，同样可以树剖。而加入或踢掉员工都可以转化为在 multiset 上加数或删数，此时单个点的 w 可能会变化，那么直接在线段树上修改即可。

现复杂度 O(n\log^2n)。

好好好，带删怎么办？

离线后发现每个员工的存在时间都是一段区间，果断时间轴上分治，就可以将删除改为撤销。同时我们在树剖上的操作正好都是可撤销的（加 / 减和加入 / 删除），因此完美适配。

至此，我们在 O(n\log^3n) 的复杂度解决了这个问题！

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
inline ll rd(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
#define d rd()
ll Sid;
ll n,m,k;
//树剖
ll dfn[100010],sz[100010],son[100010];
ll de[100010],fa[100010],top[100010],rk[100010];
vector<ll>e[100010];
void dfs1(ll u,ll f){
    de[u]=de[f]+1,fa[u]=f;sz[u]=1;
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(v==f)continue;
        dfs1(v,u);sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}ll TIm;
void dfs2(ll u,ll tp){
    top[u]=tp;dfn[u]=++TIm;rk[TIm]=u;
    if(son[u])dfs2(son[u],tp);
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
ll t[100010<<2];//min(size-ssum of empolees)
ll tid[100010<<2];//id of min
ll tg[100010<<2];//tag of t
multiset<ll>st[100010];
ll w[100010<<2];//min value of employees
ll wid[100010<<2];//id of min w
void upd(ll p){
    if(t[rs(p)]<=t[ls(p)])t[p]=t[rs(p)],tid[p]=tid[rs(p)];
    else t[p]=t[ls(p)],tid[p]=tid[ls(p)];
    if(w[rs(p)]<=w[ls(p)])w[p]=w[rs(p)],wid[p]=wid[rs(p)];
    else w[p]=w[ls(p)],wid[p]=wid[ls(p)];
}
void build(ll l,ll r,ll p){
    if(l==r){t[p]=sz[rk[l]];w[p]=0x3f3f3f3f3f3f3f3f;tid[p]=wid[p]=l;return;}
    ll mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    upd(p);
}
void pd(ll p){
    if(!tg[p])return;
    t[ls(p)]+=tg[p],t[rs(p)]+=tg[p];
    tg[ls(p)]+=tg[p],tg[rs(p)]+=tg[p];
    tg[p]=0;
}
void add(ll l,ll r,ll p,ll L,ll R,ll k){
    if(L<=l&&r<=R){t[p]+=k,tg[p]+=k;return;}
    pd(p);ll mid=l+r>>1;
    if(mid>=L)add(l,mid,ls(p),L,R,k);
    if(mid<R)add(mid+1,r,rs(p),L,R,k);
    upd(p);
}
void ch(ll l,ll r,ll p,ll pos,ll k,ll o){
    if(l==r){
        if(o==0)st[l].insert(k);
        else st[l].erase(st[l].find(k));
        if(st[l].size())w[p]=*st[l].begin();
        else w[p]=0x3f3f3f3f3f3f3f3f;return;
    }pd(p);ll mid=l+r>>1;
    if(mid>=pos)ch(l,mid,ls(p),pos,k,o);
    if(mid<pos)ch(mid+1,r,rs(p),pos,k,o);
    upd(p);
}inline pair<ll,ll> Min(pair<ll,ll> a,pair<ll,ll>b){
    if(a.first!=b.first)return min(a,b);
    if(a.second>b.second)return a;return b;
}
pair<ll,ll> mnt(ll l,ll r,ll p,ll L,ll R){
    if(L<=l&&r<=R)return {t[p],tid[p]};
    pd(p);ll mid=l+r>>1;pair<ll,ll>ans={0x3f3f3f3f,0x3f3f3f3f};
    if(mid>=L)ans=Min(ans,mnt(l,mid,ls(p),L,R));
    if(mid<R)ans=Min(ans,mnt(mid+1,r,rs(p),L,R));
    return ans;
}pair<ll,ll> mnw(ll l,ll r,ll p,ll L,ll R){
    if(L<=l&&r<=R)return {w[p],wid[p]};
    pd(p);ll mid=l+r>>1;pair<ll,ll>ans={0x3f3f3f3f,0x3f3f3f3f};
    if(mid>=L)ans=Min(ans,mnw(l,mid,ls(p),L,R));
    if(mid<R)ans=Min(ans,mnw(mid+1,r,rs(p),L,R));
    return ans;
}

void addch(ll u,ll v,ll k){
    while(top[u]!=top[v]){
        if(de[top[u]]<de[top[v]])swap(u,v);
        add(1,n,1,dfn[top[u]],dfn[u],k);
        u=fa[top[u]];
    }if(dfn[u]>dfn[v])swap(u,v);
    add(1,n,1,dfn[u],dfn[v],k);
}
pair<ll,ll> chmnt(ll u,ll v){
    pair<ll,ll>ans={0x3f3f3f3f,0x3f3f3f3f};
    while(top[u]!=top[v]){
        if(de[top[u]]<de[top[v]])swap(u,v);
        ans=Min(ans,mnt(1,n,1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }if(dfn[u]>dfn[v])swap(u,v);
    ans=Min(ans,mnt(1,n,1,dfn[u],dfn[v]));
    return ans;
}
pair<ll,ll> mnw(ll u){
    return mnw(1,n,1,dfn[u],dfn[u]+sz[u]-1);
}ll SUM;

struct node{
    ll u,x;
    ll isf,iss;
    ll pos;
    ll delf,dels;
};
//加入员工
void addemp(node &p,ll u,ll x){
    p.u=u,p.x=x;
    // cout<<"----------------\nadd ("<<u<<","<<x<<")\n";
    pair<ll,ll>is=chmnt(1,u);
    p.isf=is.first,p.iss=is.second;
    if(is.first!=0){
        // cout<<"all ancectors are unfull.\n";
        SUM+=x;ch(1,n,1,dfn[u],x,0);addch(1,u,-1);
        return;
    }ll pos=rk[is.second];p.pos=pos;
    // cout<<"nearst full ancestor is "<<pos<<endl;

    pair<ll,ll>del=mnw(pos);
    p.delf=del.first,p.dels=del.second;
    if(del.first>x)return;
    // cout<<"min value of emploees: ("<<rk[del.second]<<","<<del.first<<")\n";
    if(del.first)addch(1,rk[del.second],1),ch(1,n,1,del.second,del.first,1);
    SUM-=del.first;SUM+=x;ch(1,n,1,dfn[u],x,0);
    addch(1,u,-1);
}
ll U[200010],X[200010];
struct ask{ll o,x,y;}q[100010];
//线段树分治
vector<ll>tr[100010<<2];
ll Ol[200010],Or[200010];
void ADD(ll l,ll r,ll p,ll L,ll R,ll o){
    if(L<=l&&r<=R){tr[p].push_back(o);return;}
    ll mid=l+r>>1;if(mid>=L)ADD(l,mid,ls(p),L,R,o);
    if(mid<R)ADD(mid+1,r,rs(p),L,R,o);
}

void get(ll l,ll r,ll p){
    vector<node>del;del.clear();
    for(int j=0;j<tr[p].size();j++){
        // cout<<l<<" "<<r<<" "<<p<<" ";
        ll i=tr[p][j];ll u=U[i],x=X[i];
        // cout<<"("<<u<<","<<x<<")\n";
        node o={0,0,0,0,0,0,0};addemp(o,u,x);
        del.push_back(o);
    }
    if(l==r)printf("%lld ",SUM);
    ll mid=l+r>>1;if(l!=r)get(l,mid,ls(p)),get(mid+1,r,rs(p));
    for(int i=del.size()-1;i>=0;i--){
        node o=del[i];ll u=o.u,x=o.x;
        if(o.isf!=0){
            addch(1,u,1);ch(1,n,1,dfn[u],x,1);SUM-=x;
        }else if(o.delf>x)continue;
        else{
            addch(1,u,1);
            SUM+=o.delf;SUM-=x;ch(1,n,1,dfn[u],x,1);   
            if(o.delf)addch(1,rk[o.dels],-1),ch(1,n,1,o.dels,o.delf,0);
        }
    }
}
int main(){
    // freopen("transfer15.in","r",stdin);
    // freopen("transfer.out","w",stdout);
    Sid=d;n=d,k=d,m=d+1;
    f(i,2,n)e[d].push_back(i);
    dfs1(1,0),dfs2(1,1);build(1,n,1);
    f(i,1,k)Ol[i]=1,Or[i]=m,U[i]=d,X[i]=d;
    f(i,2,m){
        ll o=d;if(o==1){
            ll u=d,x=d;q[i]={o,u,x};k++;
            U[k]=u,X[k]=x,Ol[k]=i,Or[k]=m;
        }else{
            ll x=d;q[i]={o,x,0};
            Or[x]=i-1;
        }
    }
    f(i,1,k)ADD(1,m,1,Ol[i],Or[i],i);
    get(1,m,1);
    return 0;
}