题解：P10560 [ICPC2024 Xi'an I] Holes and Balls

honglan0301 · 2024-06-01 21:49:08 · 题解

我好像秒了。

分析

<0> 记 q_i 为 p_i 的逆排列。则显然地，一种填数方式合法当且仅当对于每个节点 i 都有 q_{a_i}=\min\limits_{j\in\text{subtree}_i}\{q_{a_j}\}。

<1> 对于最小化字典序问题，显然要从前往后逐位确定。那么我们需要解决的问题变为，在 q_{a_j(j<i)} 均已确定的情况下，求出 p_{q_{a_i}} 可能的最小值。那么：

首先考虑判定，即判断 q_{a_i} 是否可以为 k：

记 lim_i 表示 i 所有已确定的祖先 j 中 q_{a_j} 的最大值。由于题目保证 fa_i(fa_i<i) 已被确定，那么只需满足三个要求，一是需要 \forall j<i,\ k\neq q_{a_j}，二是需要 k>lim_i，三是需要能够把 [lim_i+1,k-1] 这些球全都填到 i 子树外面。

对于第三个要求，我们注意到这些球显然能填就填，那么类似拓扑排序地，对于每个祖先均被填过的 j (j\neq i)，在处理到第 lim_j 个球时将其加入队列，容易做到 O(n) 判定。
观察结论：

由判定过程可知，q_{a_i} 的可能值是一段区间 [l,r]（再去掉已被使用过的 q_{a_j} (j<i)），其中 l=lim_i+1，我们只需快速求出区间右端点 r。
观察结论：

考虑这样一种刻画。记录 cnt_i=\sum\limits_{j\notin \text{subtree}_i} [lim_j=i] 及其前缀和数组 sum_i，则可以确定 r=\min\{i|sum_i<i\}。

证明：一方面，sum_i<i 意味着第 i 个球一定无处可填，即 r\leq i；另一方面，当 \forall j<i,\ sum_j\geq j 时，由于题目保证 \forall x<y,dep_x \leq dep_y（已确定的点一定形成包含根的连通块），对子树外未确定的点按照 (lim,dep) 双关键字排序后依次填入球一定合法，因此 r=i。
那么此时可以做到 O(n) 时间确定一位，总复杂度 O(n^2)。

<2> 考虑优化。目前的时间复杂度瓶颈有两处，分别是求右端点 r 和区间求未被选择的数的 \min。

后者可以使用线段树简单处理。只需单点修改（每次把被选择的数改成充分大的数）+区间求 \min，时间复杂度 O(n\log n)。
前者可以利用题目条件。注意到题目保证 \forall x<y,dep_x\leq dep_y，这意味着每次确定一个数时，其子树内所有点的 lim 均相同。因此对权值考虑，维护 sum_i-i，只需支持“后缀加减，求第一个值为负数的下标”，可以在维护区间加区间 \min 的线段树上二分实现，时间复杂度 O(n\log n)。
综上，总时间复杂度 O(n\log n)，可以通过本题。

代码

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long

int n,u,v,fa[500005],dep[500005],sz[500005],ans[500005];
int pp[500005],usd[500005],wz[500005];
vector <int> e[500005];

void dfs0(int x,int fat)
{
    sz[x]=1;
    for(auto i:e[x])
    {
        if(i==fat) continue;
        dep[i]=dep[x]+1; fa[i]=x; dfs0(i,x); sz[x]+=sz[i];
    }
}

struct tree1
{
    pair<int,int> mn;
}tree1[2000005];

#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define m(x) tree1[x].mn
#define md(x,y) ((x+y)>>1)
#define push_up1(x) m(x)=min(m(ls(x)),m(rs(x)))

void build1(int l,int r,int p)
{
    if(l==r) return m(p)=mp(pp[l],l),void(); int mid=md(l,r);
    build1(l,mid,ls(p)); build1(mid+1,r,rs(p)); push_up1(p);
}
void cz1(int l,int r,int x,int p)
{
    if(l==r) return m(p)=mp(10000000,l),void(); int mid=md(l,r);
    if(mid>=x) cz1(l,mid,x,ls(p)); else cz1(mid+1,r,x,rs(p)); push_up1(p);
}
pair<int,int> ask1(int l,int r,int x,int y,int p)
{
    if(l>=x&&r<=y) return m(p); int mid=md(l,r); pair<int,int> na=mp(10000000,0);
    if(mid>=x) na=min(na,ask1(l,mid,x,y,ls(p))); if(mid<y) na=min(na,ask1(mid+1,r,x,y,rs(p))); return na;
}

struct tree2
{
    int mn,tagadd;
}tree2[2000005];

#define n(x) tree2[x].mn
#define push_up2(x) n(x)=min(n(ls(x)),n(rs(x)));
#define tg(x) tree2[x].tagadd

void cza(int k,int p) {n(p)+=k; tg(p)+=k;}
void push_down(int p) {cza(tg(p),ls(p)); cza(tg(p),rs(p)); tg(p)=0;}

void build2(int l,int r,int p)
{
    if(l==r) return n(p)=n-l,void(); int mid=md(l,r);
    build2(l,mid,ls(p)); build2(mid+1,r,rs(p)); push_up2(p);
}
void cza(int l,int r,int x,int y,int k,int p)
{
    if(l>=x&&r<=y) return cza(k,p),void(); int mid=md(l,r); push_down(p);
    if(mid>=x) cza(l,mid,x,y,k,ls(p)); if(mid<y) cza(mid+1,r,x,y,k,rs(p)); push_up2(p);
}
int ask2(int l,int r,int p)
{
    if(l==r) return l; int mid=md(l,r); push_down(p);
    if(n(ls(p))<0) return ask2(l,mid,ls(p)); else return ask2(mid+1,r,rs(p));
}

/*int cnt[500005]; 这是赛时用来验证正确性的暴力。
void dfs1(int x,int fat,int lim)
{
    lim=max(lim,wz[x]);
    cnt[lim]++;
    for(auto i:e[x])
    {
        if(i==fat) continue;
        dfs1(i,x,lim);
    }
}
int calc(int x)
{
    wz[x]=n+1;
    for(int i=1;i<=n;i++) cnt[i]=0;
    dfs1(1,1,1);
    for(int i=1;i<=n;i++)
    {
        cnt[i]+=cnt[i-1]; if(cnt[i]<i) return i;
    }
    return n;
}*/
void solve(int x)
{
    if(x==1) {return ans[x]=pp[1],wz[x]=1,usd[1]=1,cz1(1,n,1,1),void();}
    int nl=wz[fa[x]];
    cza(1,n+1,wz[fa[x]],n+1,-sz[x],1);
    cza(1,n+1,n+1,n+1,sz[x],1);
    int nr=ask2(1,n+1,1);
    pair<int,int> na=ask1(1,n,nl,nr,1);
    ans[x]=pp[na.se],wz[x]=na.se,usd[na.se]=1,cz1(1,n,na.se,1);
    cza(1,n+1,n+1,n+1,-sz[x],1);
    cza(1,n+1,na.se,n+1,sz[x],1);
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pp[i];
    for(int i=1;i<=n-1;i++) cin>>u>>v,e[u].pb(v),e[v].pb(u);
    dfs0(1,1);
    build1(1,n,1);
    build2(1,n+1,1);
    for(int i=1;i<=n;i++) solve(i);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl;
}