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

· · 题解

题意

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

思路

可以发现 x_i 战胜 y_i 后，y_i 的所有奖牌的后续奖牌持有者的变化情况与 x_i 的一致，可以联想两个节点在深度为 LCA 以上的祖先节点一致，故考虑建一个森林，节点 u 代表奖牌 u，id_u 为在奖牌 u 所有者改变前奖牌 u 的所有者，val_u 为改变前持有奖牌 u 的时间，则对于样例 2 可以建出如下森林：

其中节点左边为 id_u，右边为 val_u。可以发现奖牌 u 被每个持有的时间与祖先相关，具体的，设 tim_i 为奖牌 u 被 i 持有的时间，则 u 的 tim 为在其父亲的 tim 的基础上令 tim_{id_u}\gets tim_{id_u}+val_u，线段树维护即可。时间复杂度 O(m\log n)。

通过记录

代码

#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;
}