专栏文章

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

__Weslie_
P9464题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mimzqour
此快照首次捕获于
2025/12/01 18:12
3 个月前
此快照最后确认于
2025/12/01 18:12
3 个月前
查看原文
信心赛 T2。

Solution P9464

O⁡(nm)\operatorname{O}(nm) 暴力显然。
考虑优化暴力。我们发现，当一个人输了之后，他的奖牌将会给到胜者，一直到胜者输掉。而胜者输掉之后，他的所有奖牌又会给到打败胜者的人。假设胜者手中有 xx 块奖牌，那么这些奖牌到后面转移路径是一样的——这太浪费时间了！
于是你考虑从后往前扫一遍，到某个位置的时候记录一下最大的奖牌数和谁拥有最大的奖牌数，然后转移的时候从当前胜者失败的位置转移即可。但是你会发现样例 33 就是错误的，因为这个无法处理一个人在不同两段之内拿到一块奖牌的情况。
于是考虑对每个时间（下文记作“位置”）开一个 map 维护，但是显然 MLE。
你要考虑我们空间复杂度的瓶颈在什么地方。如果 xix_i 的失败位置确定是 i+1i+1（即 yi+1=xiy_{i+1}=x_i），那么你就不需要对每个位置开一个 map 了，转移的时候直接修改 i+1i+1 位置的 map 即可。
但是现实很骨感，我们无法保证上面的性质，导致了我们转移可能需要任何一个位置的 map 的信息。
于是我们考虑换一种顺序遍历。
看这张图。如果我们在图的右边加一个超级汇点：
然后整个图形成了一个每条边都链接了时间 ii 和 xix_i 失败时间的树形结构。
看不懂？给你换一种方式看：
然后我们遍历这颗树，这棵树上有边权。边权是一个二元组 (x,y)(x,y)，表示第 xx 个人时间增加 yy。
由于子树内的点出来必然走过这条边，所以可以直接往上加，遍历完这棵子树之后再去掉这条边的影响即可。
那么你现在需要维护一个全局 max⁡\max 位置和单点修改的东西，显然是线段树，然后你做完了。
CodeCPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
using namespace std;
const int N=200005;
const int mod=1;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
int x[N],y[N],nxt[N];
int mx[N],pos[N],ans[N];
int n,m;
vector<int>g[N];
struct node{
	int u,v,ps;int nxt;
	ll w;
}e[N<<1];
int head[N],cnt;
void add(int u,int v,int ps,ll w){
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].ps=ps;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
struct segtree{
	int tr[N<<2],mxp[N<<2];
	void pushup(int now){
		if(tr[ls]>=tr[rs]){
			tr[now]=tr[ls];
			mxp[now]=mxp[ls];
		}
		else{
			tr[now]=tr[rs];
			mxp[now]=mxp[rs];
		}
	}
	void build(int l,int r,int now){
		if(l==r){
			mxp[now]=l;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,ls);
		build(mid+1,r,rs);
		pushup(now);
	}
	void update(int l,int r,int pos,int now,int x){
		if(l==r){
			tr[now]+=x;
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)update(l,mid,pos,ls,x);
		if(pos>mid)update(mid+1,r,pos,rs,x);
		pushup(now);
	}
}tr;
void dfs(int now,int fa){
	if(now!=m+1)ans[tr.mxp[1]]++;
	for(int i=head[now],v;i;i=e[i].nxt){
		v=e[i].v;
		if(v==fa)continue;
		tr.update(1,n,e[i].ps,1,e[i].w);
		dfs(v,now);
		tr.update(1,n,e[i].ps,1,-e[i].w);
	}
}
signed main(){
//	freopen("contest.in","r",stdin);
//	freopen("contest.out","w",stdout);
	fastio;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
		x[i]++;y[i]++;
		g[x[i]].push_back(i);
		for(auto x:g[y[i]]){
			nxt[x]=i;
		}
		g[y[i]].clear();
	}
	for(int i=1;i<=n;i++){
		for(auto x:g[i]){
			nxt[x]=m+1;
		}
	}
	tr.build(1,n,1);
	for(int i=1;i<=m;i++){
		add(nxt[i],i,x[i],nxt[i]-i);
		add(i,nxt[i],x[i],nxt[i]-i);
	}
	dfs(m+1,0);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<' ';
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...