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

vectorwyx · 2023-04-11 10:45:44 · 题解

由题意可知，最终调度方案里，对于同一部门的员工，只需要保留能力值最大的，其余员工不会产生贡献，我们视为他们被淘汰了。那么有一个简单的贪心：像树形 dp 那样自底向上维护每棵子树的最优调度策略。对于叶节点，最优策略就是保留这个结点上能力值最大的那位员工。对于一个非叶结点 x，我们先求出它的所有儿子对应子树的最优策略，然后挨个考察初始位置在 x 上的所有员工 i，如果 x 的整棵子树里还有结点空闲着，那就把员工 i 调度到这个空闲的结点上。否则，找出目前 x 子树中能力值最小的那位员工，比较他与员工 i 的能力值，如果员工 i 的能力值更大就淘汰掉这位员工，腾出位置，把员工 i 调度过去。这个贪心的正确性显然。

注意到由于是自底向上进行的，我们其实并不关心每个员工究竟调度到了哪个结点，只需要关心当前子树中有哪些员工幸存了下来。更进一步地，我们其实是对每个结点 x 维护了一个有序序列，把 x 所有儿子的序列合并起来再加上初始时位置在 x 的所有员工得到序列 a，令 c 为 a 序列的长度，把 a 按能力值降序排列后淘汰掉末尾的 \max(0,c-s_x) 个员工就得到了 x 对应的序列（s_x 为 x 的子树大小），淘汰 \max(0,c-s_x) 个员工是因为我们必须保证幸存的员工数量不超过子树大小。这个过程显然可以用可并堆来实现，令员工数为 k，单次复杂度为 O(n+k\log k)，总复杂度为 O(mn+mk\log k)，可以获得 48 分，这里给出了代码实现（采用的是 pb_ds 库的配对堆）。

接下来的方向是想办法快速维护这个合并的过程。先来看看只加点怎么做，此时，对于一位在之前的合并过程中被淘汰的员工，他之后肯定也没有机会复活，所以只需要维护那些当前还没被淘汰的员工。换言之，边加点，边维护每个结点 x 的序列。我们称结点 x 是满的，当且仅当 x 的序列大小恰好等于 s_x。假设现在要在结点 x 新加入一位员工 i，考虑他对于 x 的祖先的序列的影响。

第一种情况是，x 到根结点的链上没有结点是满的，此时加入员工 i 后 x 的祖先结点在合并序列时一定不会发生超载的情况，所以不会有员工被淘汰。那么员工 i 对祖先的影响仅仅是在对应序列中多加了一位员工。

第二种情况是，x 到根结点的链上存在一些结点是满的，那员工 i 的加入势必会引起淘汰的发生。假装模拟这个向上合并的过程，显然第一次淘汰会发生在 x 的祖先中距离 x 最近的那个满的结点，记为 y。y 的序列的大小恰为 s_x，我们找出这个序列中最末尾的员工 j（也就是能力值最小的），如果员工 i 的能力值比员工 j 都要小，那他的旅途到这就戛然而止了，j 会把 i 淘汰掉。而如果员工 i 的能力值大于等于员工 j，那么把员工 j 替换成员工 i 肯定更优，而且根据单调性，员工 j 没有在之后的合并过程中被淘汰，所以用 i 换掉 j 后 i 也一定不会被淘汰，所以我们根本不用再考虑后面的过程了。

那么现在的问题变成了，单点修改，查询 x 祖先中距离 x 最近的满的结点，查询子树最小值。再转化一下，初始时每个结点 x 有一个权值 v_x=s_x，然后每在 x 结点加一个新员工就会把 x 到根的链上的结点的权值 -1，问祖先中最近的权值等于 0 的点。这其实就是链加链 \min，树剖一下，复杂度是 O((k+m)\log^2 n)。

现在我们搞出了只加点时的做法，由于询问并不强制在线，套一层线段树分治即可变删除为撤销，视 n,m,k 同阶的话则复杂度为 O(n\log^3 n)，如果将链加链 \min 改用静态 LCT 实现即可变为 O(n\log^2 n)。不过树剖的常数还是蛮小的，完全可过。

代码如下：

#include<bits/stdc++.h>
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define gc getchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
template<typename T> void out(T *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=1e5+5,inf=1e9;
struct People{
    int x,v;
    People(){x=0,v=inf;}
    bool operator<(const People &y)const{re v<y.v;}
    bool operator>(const People &y)const{re v>y.v;}
}a[N<<1];
vector<int> e[N];
int n,m,k,dfn[N],rk[N],ti,siz[N],son[N],Tid,top[N],lst[N<<1],fa[N];

void dfs1(int x){
    siz[x]=1;
    int mx=0;
    for(int i:e[x]){
        dfs1(i);
        siz[x]+=siz[i];
        if(siz[i]>mx) mx=siz[i],son[x]=i;
    }
}

void dfs2(int x,int t){
    top[x]=t;
    dfn[x]=++ti;rk[ti]=x;
    if(son[x]) dfs2(son[x],t);
    for(int i:e[x]) if(i!=son[x]) dfs2(i,i);
}

#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
namespace DS1{//维护子树最小值
//auto cmp=[](int x,int y){re a[x]<a[y];};
//priority_queue<int,vector<int>,decltype(cmp)> pq[N];
struct qwq{
    int id;
    qwq(){id=0;}
    qwq(int o){id=o;}
    bool operator<(const qwq &x)const{
        if(a[id].v!=a[x.id].v) re a[id]<a[x.id];
        re id<x.id;
    }
};
set<qwq> pq[N];
int tr[N<<2];
void ps(int x){
    if(a[tr[ls]]<a[tr[rs]]) tr[x]=tr[ls];
    else tr[x]=tr[rs];
}
void upd(int x,int l,int r,int aim,int k){
    if(l==r){
        tr[x]=k;
        re;
    }
    if(aim<=mid) upd(ls,l,mid,aim,k);
    else upd(rs,mid+1,r,aim,k);
    ps(x);
}

int ask(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R) re tr[x];
    if(R<=mid) re ask(ls,l,mid,L,R);
    if(L>mid) re ask(rs,mid+1,r,L,R);
    int wl=ask(ls,l,mid,L,R);
    int wr=ask(rs,mid+1,r,L,R);
    if(a[wl]>a[wr]) re wr;
    re wl;
}

void ins(int id){
    int x=a[id].x;
    pq[x].insert(qwq(id));
    upd(1,1,n,dfn[x],(*pq[x].begin()).id);
}
void del(int id){
    int x=a[id].x;
//  assert(id==pq[x].top().id);
    pq[x].erase(qwq(id));
    if(pq[x].empty()) upd(1,1,n,dfn[x],0);
    else upd(1,1,n,dfn[x],(*pq[x].begin()).id);
}
}

namespace DS2{

namespace Sgt{
struct Node{
    int tag,mn;
    Node(){tag=0;mn=inf;}
    void upd(int x){tag+=x,mn+=x;}
}tr[N<<2];

void ps(int x){tr[x].mn=min(tr[ls].mn,tr[rs].mn);}
void pd(int x){
    int &k=tr[x].tag;
    if(!k) re;
    tr[ls].upd(k);
    tr[rs].upd(k);
    k=0;
}

void build(int x,int l,int r){
    if(l==r){
        tr[x].mn=siz[rk[l]];
        re;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    ps(x);
}

void upd(int x,int l,int r,int L,int R,int k){
//  if(x==1) printf("upd(%d,%d,%d,%d,%d,%d)\n",x,l,r,L,R,k);
    if(l>=L&&r<=R){
        tr[x].upd(k);
        re;
    }
    pd(x);
    if(L<=mid) upd(ls,l,mid,L,R,k);
    if(R>mid) upd(rs,mid+1,r,L,R,k);
    ps(x);
}

int ask(int x,int l,int r,int L,int R){
//  if(x==1) printf("Sgt::ask(%d,%d,%d,%d,%d)\n",x,l,r,L,R);
    if(l>=L&&r<=R) re tr[x].mn;
    pd(x);
    if(R<=mid) re ask(ls,l,mid,L,R);
    if(L>mid) re ask(rs,mid+1,r,L,R);
    re min(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));
}

int get(int x,int l,int r,int L,int R){
//  printf("get(%d,%d,%d,%d,%d)\n",x,l,r,L,R);
    if(l>=L&&r<=R){
        if(tr[x].mn>0) re 0;
        while(l<r){
            pd(x);
            if(tr[rs].mn==0) x=rs,l=mid+1;
            else x=ls,r=mid;
        }
        re rk[l];
    }
    pd(x);
    if(R<=mid) re get(ls,l,mid,L,R);
    if(L>mid) re get(rs,mid+1,r,L,R);
    int w=get(rs,mid+1,r,L,R);
    if(w) re w;
    re get(ls,l,mid,L,R);
}
}

void build(){
    Sgt::build(1,1,n);
}

void upd(int x,int k){
    while(x){
        int y=top[x];
        Sgt::upd(1,1,n,dfn[y],dfn[x],k);
        x=fa[y];
    }
}
int ask(int x){
    while(x){
        int y=top[x];
        if(Sgt::ask(1,1,n,dfn[y],dfn[x])>0){
            x=fa[y];
            co;
        }
        re Sgt::get(1,1,n,dfn[y],dfn[x]);
    }
    re 0;
}
} 

namespace Company{
struct Roll{
    int id,loser;
}stk[N<<1];
int top;
ll ans;

void hello_world(int id){//正式步入职业生涯 
    //Hello, world!
//  printf("hello_world(%d)!\n",id);
    ans+=a[id].v;
    DS1::ins(id);
    DS2::upd(a[id].x,-1);
}

void say_goodbye(int id){
//  printf("say_goodbye(%d)!\n",id);
    ans-=a[id].v;
    DS1::del(id);
    DS2::upd(a[id].x,1);
}

bool gao(int id){//把员工 id 加进来 
//  printf("gao(%d)\n",id);
    int t=DS2::ask(a[id].x);
    if(!t){
        ++top;
        stk[top].id=id,stk[top].loser=0;//岗位充足，没有产生下岗员工 
        hello_world(id);
        re 1;
    }
    //很遗憾，零和博弈，必定有输家
    int me=DS1::ask(1,1,n,dfn[t],dfn[t]+siz[t]-1);//末位淘汰
    if(a[me]<a[id]){//内卷斗兽场 
        ++top;
        stk[top].id=id,stk[top].loser=me;
        hello_world(id);
        say_goodbye(me);
        re 1;
    }
    re 0;
}
void roll(){
//  puts("roll_back");
    int x=stk[top].id,y=stk[top].loser;top--;
    say_goodbye(x);
    if(y) hello_world(y);
}
}

ll ans[N];
namespace DS3{//时间线段树
vector<int> tr[N<<2];
void push(int x,int l,int r,int L,int R,int id){
//  printf("push(%d,%d,%d,%d,%d,%d)\n",x,l,r,L,R,id);
    if(l>=L&&r<=R){
        tr[x].pb(id);
        re;
    }
    if(L<=mid) push(ls,l,mid,L,R,id);
    if(R>mid) push(rs,mid+1,r,L,R,id);  
}
void dfs(int x,int l,int r){
//  printf("dfs(%d,%d,%d)\n",x,l,r);
    int ct=0;
    for(int i:tr[x]) ct+=Company::gao(i);
    if(l==r) ans[l]=Company::ans;
    else dfs(ls,l,mid),dfs(rs,mid+1,r);
    while(ct--) Company::roll();
}
}

void file(){
    freopen("transfer.in","r",stdin);
    freopen("transfer.out","w",stdout);
}

signed main(){
//  file();
    cin>>Tid;
    cin>>n>>k>>m;
    fo(i,2,n) fa[i]=read(),e[fa[i]].pb(i);
    dfs1(1);
    dfs2(1,1);
//  cout<<"son:";out(son,1,n);
//  cout<<"dfn:";out(dfn,1,n);
//  cout<<"top:";out(top,1,n);
    DS2::build();
    fo(i,1,k) a[i].x=read(),a[i].v=read();
    fo(i,1,m){
        int o=read(),x=read();
        if(o==1){
            a[++k].x=x;
            lst[k]=i;
            a[k].v=read();
        }else DS3::push(1,0,m,lst[x],i-1,x),lst[x]=-1;
    }
    fo(i,1,k) if(lst[i]>-1) DS3::push(1,0,m,lst[i],m,i);
    DS3::dfs(1,0,m);
    out(ans,0,m);
    return 0;
}
}
/*
-------------------------------------------------
*/

signed main(){re vectorwyx::main();}