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

目前暂无修正。

选手无法观察到树形结构，于是选手写了比较没脑子的可持久化线段树做法。

我们考虑第 \(i\) 个奖牌会到哪里去，发现每个关系 \((X,Y)\) 意思是此时 \(Y\) 的奖牌会被 \(X\) 赢走，即奖牌此时到 \(Y\) 后会往 \(X\) 走。我们可以暴力地每个点开一个桶，下标 \(j\) 记录接下来奖牌会在第 \(j\) 个人总共停留 \(buk[j]\) 晚，每次转移 \(X\) 的桶复制给 \(Y\) 即可。

由于对不同的 \(Y\) 停留在 \(X\) 的时间不一样，还需要在 \(buk[X]\) 的位置加上当前时间与上一次 \(X\) 作为 \(Y'\) 出现的时间的差。注意：如果一个 \(Y\) 获得了多个 \(X\) 给的桶，那么只有最新的是有效的，这样是 \(O(nm)\) 的。

考虑优化这一过程，把这个桶变成动态开点线段树，找 \(\max\) 是容易的，复制的话我们采用类似可持久化线段树的思想，每次 \(rt[Y]\) 直接在 \(rt[X]\) 的基础上修改，多开 \(O(\log n)\) 个点，每次第 \(i\) 块奖牌查询直接在 \(rt[Y]\) 线段树上二分最大是哪个人。时间复杂度和空间复杂度都是 \(O(m\log n)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,m,X[N],Y[N],ans[N];
int ncnt,rt[N],lasr[N];
struct Node{int lc,rc,mx;}t[N<<5];
#define ls t[p].lc
#define rs t[p].rc
#define mid ((l+r)>>1)
void pushup(int p){t[p].mx=max(t[ls].mx,t[rs].mx);
}
void modify(int o,int &p,int l,int r,int pos,int v){p=++ncnt;t[p]=t[o];if(l==r){t[p].mx+=v;return ;}if(pos<=mid)modify(t[o].lc,ls,l,mid,pos,v);else modify(t[o].rc,rs,mid+1,r,pos,v);pushup(p);
}
int query(int p,int l,int r){if(!p)return 0;if(l==r)return l;if(t[ls].mx>=t[rs].mx)return query(ls,l,mid);return query(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;x++;y++;X[i]=x;Y[i]=y;}for(int i=1;i<=n;i++)lasr[i]=m+1;for(int i=m;i>=1;i--){int x=X[i],y=Y[i];modify(rt[x],rt[y],1,n,x,lasr[x]-i);ans[query(rt[y],1,n)]++;lasr[y]=i;}for(int i=1;i<=n;i++)cout<<ans[i]<<' ';return 0;
}