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

先不考虑插入与删除。

假设节点

x

的所有子树

v

的人员方案都已经确定了（即只考虑

v

子树时该方案是最优的），现在需要插入

x

节点的若干员工

val

。

若此时 $x$ 子树中还有空的位置，将 $val$ 插入到空的位置上一定不会使得答案更劣
若此时 $x$ 子树满了，用 $val$ 替换子树内能力值最小的 $mn$ 肯定最优。若最小的 $mn\geqslant val$ ，那么放入 $val$ 肯定不优。

以上贪心策略算是显然的。“形式化的”，设

siz_x

表示

x

子树大小，每个节点处应维护一个能力值序列，父节点

x

的能力值序列为子节点

v

的能力值序列的并 +

x

节点的能力值，若其长度超过

siz_x

则踢出最小的若干元素。

从以上过程也能看出“加点”比“删点”容易，再加上操作中的“插入——撤销”操作，考虑线段树分治插点。假设当前已维护了整棵树的答案，考虑一次新的插入

(x,val)

对答案的贡献。若值

val

会被贡献，它一定能被插入到

(rt,x)

的所有能力值序列中或替换掉原本的某个值。

若 $(rt,x)$ 上的点的所有子树都不满，那么 $val$ 一定可以插入至最终的序列中
否则，考虑 $val$ 会被哪个点“拦截”下来，即考虑 $x$ 最深的满子树祖先 $fa$ ;此时 $val$ 要么被覆盖要么替换掉 $fa$ 树中被选的最小值 $mn$ ，若 $mn<val$ 那么 $val$ 就会替换答案序列中的 $mn$ 并贡献答案增量 $val-mn$ ，否则 $val$ 会被覆盖然后死翘翘。考虑最深的满子树节点即可，因为如果 $val$ 替换掉了 $mn$ 导致它在某个祖先处被覆盖，被覆盖这个 $mn$ 一定不会在答案序列中

思路说到这里就很清晰了，在线段树分治的架构上用重链剖分维护链上最深的满子树点（记录

siz-选择个数

即可），再查询子树内最小值

mn

就完了，复杂度

O(n\log ^3 n)

再说下程序实现，维护子树被选最小值的方法是每个节点开个 multiset 记录该节点被选入答案序列的能力值，在线段树上放其 multiset 集合中的最小值；插入、撤销操作在 multiset 中插入/删除再给线段树节点赋值就完成了。

CPP

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fst first
#define scd second
#define mkp make_pair
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int T,n,k,m;
vector <int> tr[N];
pii a[N<<1];
int b[N<<1],f[N<<1],ans[N];
int siz[N],son[N],fa[N],dep[N];
int dfn[N],tme,idx[N],top[N];
struct Segment_Tree
{
    pii mn(pii x,pii y) { return (x.scd<y.scd?x:y); }
    struct node { int l,r,mn1,tag; pii mn2; }tr[N<<2];//mn1:siz-cnt mn2:(pos,val)
    void push_up(int id)
    {
        tr[id].mn1=min(tr[id<<1].mn1,tr[id<<1|1].mn1);
        tr[id].mn2=mn(tr[id<<1].mn2,tr[id<<1|1].mn2);
    }
    void push_down(int id)
    {
        if (!tr[id].tag) return ; 
        tr[id<<1].mn1+=tr[id].tag,tr[id<<1|1].mn1+=tr[id].tag;
        tr[id<<1].tag+=tr[id].tag,tr[id<<1|1].tag+=tr[id].tag;
        tr[id].tag=0;
    }
    void build(int id,int l,int r)
    {
        tr[id].l=l,tr[id].r=r;
        if (l==r) { tr[id].mn1=siz[idx[l]],tr[id].mn2=mkp(idx[l],inf); return ; }
        int mid=(l+r)>>1;
        build(id<<1,l,mid),build(id<<1|1,mid+1,r); push_up(id);
    }
    void update(int id,int pos,int k)
    {
        if (tr[id].l==tr[id].r) { tr[id].mn2.scd=k; return ; }
        push_down(id);
        int mid=(tr[id].l+tr[id].r)>>1;
        if (mid>=pos) update(id<<1,pos,k);
        else update(id<<1|1,pos,k); push_up(id);
    }
    int query_mn(int id,int l,int r)
    {
        if (tr[id].l>=l&&tr[id].r<=r) return tr[id].mn1;
        push_down(id); int mid=(tr[id].l+tr[id].r)>>1,res=inf;
        if (mid>=l) res=query_mn(id<<1,l,r);
        if (mid+1<=r) res=min(res,query_mn(id<<1|1,l,r));
        return res;
    }
    int tmp(int id)
    {
        if (tr[id].l==tr[id].r) return idx[tr[id].l];
        push_down(id);
        return (tr[id<<1|1].mn1?tmp(id<<1):tmp(id<<1|1));
    }
    int bs(int id,int l,int r)
    {
        if (tr[id].l>=l&&tr[id].r<=r) return (tr[id].mn1?-1:tmp(id));
        push_down(id);
        int res=-1,mid=(tr[id].l+tr[id].r)>>1;
        if (mid+1<=r) res=bs(id<<1|1,l,r);
        return (res==-1?(mid>=l?bs(id<<1,l,r):-1):res);
    }
    pii query(int id,int l,int r)
    {
        if (tr[id].l>=l&&tr[id].r<=r) return tr[id].mn2;
        push_down(id);
        int mid=(tr[id].l+tr[id].r)>>1; pii res=mkp(0,inf);
        if (mid>=l) res=query(id<<1,l,r);
        if (mid+1<=r) res=mn(res,query(id<<1|1,l,r)); return res;
    }
    void add(int id,int l,int r,int k)
    {
        if (tr[id].l>=l&&tr[id].r<=r) { tr[id].mn1+=k; tr[id].tag+=k; return ; }
        push_down(id);
        int mid=(tr[id].l+tr[id].r)>>1;
        if (mid>=l) add(id<<1,l,r,k);
        if (mid+1<=r) add(id<<1|1,l,r,k); push_up(id);
    }
}Tr;
multiset <int> st[N];
vector <pii> add[N<<2];

void dfs1(int x)
{
    siz[x]=1,dep[x]=dep[fa[x]]+1;
    int _size=tr[x].size(),v;
    for (int i=0;i<_size;i++)
    {
        dfs1(v=tr[x][i]); siz[x]+=siz[v]; 
        if (siz[v]>siz[son[x]]) son[x]=v;
    }
}
void dfs2(int x,int _top)
{
    dfn[x]=++tme,idx[tme]=x,top[x]=_top;
    if (son[x]) dfs2(son[x],_top);
    int _size=tr[x].size(),v;
    for (int i=0;i<_size;i++) if ((v=tr[x][i])!=son[x]) dfs2(v,v);
}
void ins(int id,int l,int r,int ql,int qr,int x,int y)
{
    if (l>=ql&&r<=qr) { add[id].push_back(mkp(x,y)); return ; }
    int mid=(l+r)>>1; if (mid>=ql) ins(id<<1,l,mid,ql,qr,x,y);
    if (mid+1<=qr) ins(id<<1|1,mid+1,r,ql,qr,x,y);
}
int query(int now)//寻找最深的满子树点
{
    while (now)
    {
        if (!Tr.query_mn(1,dfn[top[now]],dfn[now])) return Tr.bs(1,dfn[top[now]],dfn[now]);
        now=fa[top[now]];
    }
    return -1;
}
void update(int x,int k) { while (x) { Tr.add(1,dfn[top[x]],dfn[x],k); x=fa[top[x]]; } }
void ad(int x,int y) { st[x].insert(y); Tr.update(1,dfn[x],*st[x].begin()); update(x,-1); }
void dl(int x,int y) { st[x].erase(st[x].lower_bound(y)); Tr.update(1,dfn[x],*st[x].begin()); update(x,1); }
void solve(int id,int l,int r,int sum)//线段树分治
{
    vector <pii> a1,a2;//记录撤销的点
    int _size=add[id].size();
    
    for (int i=0;i<_size;i++)
    {
        int pos=add[id][i].fst,val=add[id][i].scd;
        int tmp=query(pos);
        if (tmp==-1) { sum+=val; ad(pos,val); a2.push_back({pos,val}); }
        else
        {
            pii res=Tr.query(1,dfn[tmp],dfn[tmp]+siz[tmp]-1);
            if (res.scd>=val) continue;
            ad(pos,val),dl(res.fst,res.scd),sum+=val-res.scd;
            a1.push_back(res),a2.push_back(add[id][i]);
        }
    }
    int mid=(l+r)>>1;
    if (l==r) cout<<sum<<" ";
    else solve(id<<1,l,mid,sum),solve(id<<1|1,mid+1,r,sum);

    _size=a1.size(); for (int i=_size-1;i>=0;i--) ad(a1[i].fst,a1[i].scd);
    _size=a2.size(); for (int i=_size-1;i>=0;i--) dl(a2[i].fst,a2[i].scd);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin>>T>>n>>k>>m; for (int i=1;i<=n;i++) st[i].insert(inf);
    for (int i=2;i<=n;i++) { cin>>fa[i]; tr[fa[i]].push_back(i); }
    for (int i=1,u,v;i<=k;i++) cin>>a[i].fst>>a[i].scd;
    for (int i=1,op,u,v;i<=m;i++)
    {
        cin>>op>>u; if (op==1) { cin>>v; a[++k]={u,v}; b[k]=i; }
        else { ins(1,0,m,b[u],i-1,a[u].fst,a[u].scd); f[u]=1; }
    }

    for (int i=1;i<=k;i++) if (!f[i]) ins(1,0,m,b[i],m,a[i].fst,a[i].scd);
    dfs1(1),dfs2(1,1); Tr.build(1,1,n),solve(1,0,m,0); return 0;
}

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

文章操作

相关推荐

评论

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