P9464 [EGOI 2023] Padel Prize Pursuit / 追梦笼式网球 题解

link T1 desu

这里给一个和其他题解不一样的建树思路。

显然我们可以发现，在某个人 $x$ 成为被打败的对象之前，他是不断收集其他人的奖牌的。

这启示我们考虑将这些其他人的奖牌一起全部临时挂载到 $x$ 上，包括本轮最新获得的奖牌也挂到 $x$ 上。

然后等有某个 $z$ 打败了 $x$ 时，再新建一个点 $p$，把 $x$ 下的点真正给到 $p$。然后把 $p$ 挂给 $z$。

那么这个 $p$ 显然就可以由 $i$ 来当了，这样同时可以维护时间戳。

此时我们还需要维护到达每个点时此时占有的人是谁。新建点 $p$ 时 $x$ 下的点即将转让给 $z$，那么自然就保存 $z$。

考虑在最后时把所有临时挂载的都给到 $m+1$，然后就从 $m+1$ 开始 dfs 下去，树上差分维护桶即可。

代码：

int n,m;
vector<int> sons[maxn];
vector<int> rts[maxn];//存放临时挂载的点
int belong[maxn];
void input(){
	n=read();m=read();
	for(int i=1;i<=m;++i){
		int x=read()+1,y=read()+1;
		for(auto p: rts[y]){
			sons[i].emplace_back(p);//让临时挂载的给到i
		}
		rts[y].clear();
		rts[x].emplace_back(i);
		belong[i]=x;
	}
	for(int i=1;i<=n;++i){
		for(auto p: rts[i]){
			sons[m+1].emplace_back(p);
		}
		rts[i].clear();
	}
}

int btime[maxn];//奖牌在每个人手中的时间
int giveto[maxn];
void dfs(int x,int mxp){
	if(x!=m+1){
		if(btime[belong[x]]>btime[mxp]) mxp=belong[x];
		else if(btime[belong[x]]==btime[mxp]&&belong[x]<mxp) mxp=belong[x];
        //上面是取btime的max的O(1)操作
		giveto[x]=mxp;//奖牌最终的归属
	}
	for(auto y: sons[x]){
		btime[belong[y]]+=x-y;//x-y即belong[y]占有的时间
		dfs(y,mxp);
		btime[belong[y]]-=x-y;
	}
}

int ans[maxn];
void solve(){
	for(int i=1;i<=m;++i){
		++ans[giveto[i]];
	}
	for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}

int main(){
	input();
	dfs(m+1,0);
	solve();
	return 0;
}

sub

392ms，跑得比另外两篇的解法多100ms，大抵是因为vector吧。