1 条题解

  • 0
    @ 2025-8-24 22:45:59

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar vectorwyx
    打 OI 就像心跳一样自然，退役就像去世一样必然。

    搬运于2025-08-24 22:45:59，当前版本为作者最后更新于2023-04-11 10:45:44，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

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

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

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

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

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

    现在我们搞出了只加点时的做法，由于询问并不强制在线，套一层线段树分治即可变删除为撤销，视 n,m,kn,m,k 同阶的话则复杂度为 O(nlog⁡3n)O(n\log^3 n)，如果将链加链 min⁡\min 改用静态 LCT 实现即可变为 O(nlog⁡2n)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();}
    • 1

    [省选联考 2023] 人员调度

    信息

    ID
    8545
    时间
    5000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 25ms