专栏文章

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

OOneLeft
P9464题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minj5j32
此快照首次捕获于
2025/12/02 03:16
3 个月前
此快照最后确认于
2025/12/02 03:16
3 个月前
查看原文

题意

有 nn 个人和 mm 次比赛，第 ii 次比赛 xix_i 赢了 yiy_i，而 yiy_i 的所有奖牌归 xix_i 且 xix_i 获得编号为 i−1i-1 的奖牌。所有比赛结束后编号 ii 的奖牌会发放给持有其时间最长的人，有多个人则给编号最小的，求每个人获得的奖牌数量。

思路

可以发现 xix_i 战胜 yiy_i 后，yiy_i 的所有奖牌的后续奖牌持有者的变化情况与 xix_i 的一致，可以联想两个节点在深度为 LCA 以上的祖先节点一致，故考虑建一个森林，节点 uu 代表奖牌 uu，iduid_u 为在奖牌 uu 所有者改变前奖牌 uu 的所有者，valuval_u 为改变前持有奖牌 uu 的时间，则对于样例 22 可以建出如下森林：
其中节点左边为 iduid_u，右边为 valuval_u。可以发现奖牌 uu 被每个持有的时间与祖先相关，具体的，设 timitim_i 为奖牌 uu 被 ii 持有的时间，则 uu 的 timtim 为在其父亲的 timtim 的基础上令 timidu←timidu+valutim_{id_u}\gets tim_{id_u}+val_u，线段树维护即可。时间复杂度 O(mlog⁡n)O(m\log n)。
通过记录

代码

CPP
#include<bits/stdc++.h>
//#pragma GCC optimize(1,2,3,"Ofast","inline")
using namespace std;
const int N=2e5+5,inf=1e9+5;
struct sgt
{
	int maxn,id;
	friend const sgt operator+(const sgt ls,const sgt rs);
	const sgt operator+=(const sgt x){return(*this)=(*this)+x;}
};
const sgt operator+(const sgt ls,const sgt rs)
{
	if(ls.maxn>=rs.maxn)return ls;
	return rs;
}
class segment_tree
{
	#define ls (u<<1)
	#define rs (u<<1|1)
	private:
		sgt node[N<<2];
		void push_up(int u){node[u]=node[ls]+node[rs];}
	public:
		void init(int u,int l,int r)
		{
			if(l==r)node[u].id=l;
			else
			{
				int mid=l+r>>1;
				init(ls,l,mid),init(rs,mid+1,r);
				push_up(u);
			}
		}
		void update(int u,int l,int r,int x,int k)
		{
			if(l==r)node[u].maxn+=k;
			else
			{
				int mid=l+r>>1;
				if(x<=mid)update(ls,l,mid,x,k);
				else update(rs,mid+1,r,x,k);
				push_up(u);
			}
		}
		sgt query(){return node[1];}
	#undef ls
	#undef rs
}tree;
vector<int>edge[N];
void build(int u,int v){edge[u].emplace_back(v);}
int id[N],val[N],num[N],lst[N],ans[N];
bool vis[N];
void dfs(int n,int u)
{
	vis[u]=true;
	tree.update(1,1,n,id[u],val[u]);
	ans[tree.query().id]++;
	for(int v:edge[u])dfs(n,v);
	tree.update(1,1,n,id[u],-val[u]);
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)
	{
		cin>>x>>y,x++,y++;
		if(lst[x]!=0)val[num[x]]=i-lst[x],build(i,num[x]);
		if(lst[y]!=0)val[num[y]]=i-lst[y],build(i,num[y]),num[y]=lst[y]=0;
		lst[x]=i,num[x]=i,id[i]=x;
	}
	tree.init(1,1,n);
	for(int i=1;i<=n;i++)
		if(num[i]&&!vis[num[i]])val[num[i]]=m-lst[i]+1,dfs(n,num[i]);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
//	freopen("ybt.in","r",stdin);
//	freopen("ybt.out","w",stdout);
	int T=1;
	for(;T;T--)solve();
	return 0;
}

评论

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

正在加载评论...