题解：P17240 [IOI 2026] 弹球机 / ballmachine

· · 题解

做一做赵大哥绝杀，何大哥差点调完，xqw 没想出来的题。

47pts

考虑从大到小对一个叶子 x 不断加入值为 x 的球，这样就出来一种类似进行了链剖分的树，设节点 u 的颜色为 a，那么下次出现颜色 a 的位置 v 一定是其儿子（没有说明 u 是叶子），中间是 u 若干个子树，可以直接得到树结构。

更深刻的刻画！

考虑刚才我们如何区分一条相同链上其他的子树，就相当于假设 u,v 在一条链剖分的链上且 u 为 v 父亲，我们期望走到 v 的时候已经走完/还没走过其他子树，这样可以使得遍历完整条链的样子，那么每条链结构类似 [1,[],2,[],2,\dots,3] 状物，其中 1,2,3 分别代表起点，中间点，终点，[] 代表一个子结构，这是一个类似欧拉序的东西，这样可以用栈直接把树的形态还原出来。

由于不只需要树的形态，我们还要记录叶子的编号，所以我们需要再来 \sqrt{m} 个状态来表示叶子编号，具体的，设置一个权值 k，每个 i=a_ik+b_i ，将 a_i,k,k+b_i+1 分别作为 1,2,3，这样匹配时能直接算出叶子编号，容易发现 k 设在 \sqrt{m} 附近最佳。 这样我们只用 c=2\sqrt{m} 就可以得到解了吗？

corner case

注意到我们可能有长度为 1 的链，这样便衰了，打个补丁，我们可以在 123 的构造上改为 1(1.5)23，1.5 代表这是个单点的叶子，那么自然的想法就是在把值域上限加上至多 s 的值，从而承载下 1.5 的位置，那么 c=2\sqrt{m}+s，但是 s 不能直接取 m，不妨取 \sqrt{m}，那么 c=4\sqrt{m}？

分析

考虑其中一种情况的链数为 a，那么 c=2\sqrt{a}+2\sqrt{m-a}+1，这是一个对勾函数，上界在 2a=m 时取到，只有 2\sqrt{2m}+1! 算上取整后 c=43。

据此我们解决了此题。

代码

QOJ 版本。

#include<bits/stdc++.h>
#include "ballmachine.h"
using namespace std;
typedef long long ll;
#define pb emplace_back

namespace kanade
{

    int n,m;
    int Len[200010],id[200010],qwq[2][200010];
    int F[200010],F2[200010],Z[200010],T[200010],P[2][200010],ok[200010];
    int n1,n2,k1,k2;
    vector<int>A,B,res,ans,awa[3010];

    void upd(int o)
    {
        int len=res.size(),w=0;
        for(int i=0;i<len;i++)
        {
            F2[i]=-1;
            int x=res[i];
            if(x<k2)
            {
                F[B[k2*o+x]]=Z[w];
                continue;
            }
            else if(x<n1)
            {
                F2[i]=Z[w];
                Z[++w]=i;
                T[w]=x-k2+1;
            }
            else if(x==n1)F2[i]=Z[w],Z[++w]=i,T[w]=0;
            else 
            {
                int ls=Z[w],lp=w,dep;
                while(!T[w])w--;
                int now=k1*(T[w]-1)+x-n1-1;
                if(ok[A[now]])F[A[now]]=ls;
                w=lp,dep=Len[A[now]];
                while(!T[w])
                {
                    P[0][Z[w]]=A[now];
                    P[1][Z[w]]=--dep;
                    w--;
                }
                P[0][Z[w]]=A[now];
                P[1][Z[w]]=--dep;
                T[w--]=0;
            }
        }
        for(int i=0;i<m;i++)
        {
            if(F[i]!=-1&&ok[i])F[i]=awa[P[0][F[i]]][P[1][F[i]]],ok[i]=0;
        }
        for(int i=0;i<len;i++)
        {
            if(F2[i]==-1)continue;
            int u=awa[P[0][i]][P[1][i]],fa=awa[P[0][F2[i]]][P[1][F2[i]]];
            F[u]=fa;
        }
    }

    vector<int> main(int M)
    {
        n=0,m=M;
        for(int i=0;i<m;i++)
        {
            while(insert(i,0))Len[i]++;
            if(Len[i]>1)A.pb(i);
            else B.pb(i);
            n+=Len[i];
            ok[i]=1,F[i]=-1;
        }
        int tot=n-1;
        for(int i=0;i<m;i++)
        {
            awa[i].pb(0);
            for(int j=1;j<Len[i];j++)awa[i].pb(tot--);
        }
        ans.resize(n-1);
        collect();
        int a=A.size(),b=B.size();
        k1=max(1,(int)sqrt(a)),k2=max(1,(int)sqrt(b));
        for(int i=0;i<a;i++)
        {
            id[A[i]]=i;
            qwq[0][A[i]]=i/k1,qwq[1][A[i]]=i%k1;
        }
        for(int i=0;i<b;i++)
        {
            id[B[i]]=i;
            qwq[0][B[i]]=i/k2,qwq[1][B[i]]=i%k2;
        }
        n1=k2+(a-1)/k1+1,n2=max(0,(b-1)/k2);
        for(int o=0;o<=n2;o++)
        {
            for(auto x:A)
            {
                insert(x,k2+qwq[0][x]);
                for(int j=2;j<Len[x];j++)insert(x,n1);
                insert(x,n1+1+qwq[1][x]);
            }
            for(auto y:B)
            {
                if(qwq[0][y]!=o)continue;
                insert(y,qwq[1][y]);
            }
            res=collect();
            upd(o);
        }
        for(int i=0;i<n-1;i++)ans[i]=F[i];
        return ans;
    }
}

std::vector<int> find_structure(int M)
{
    return kanade::main(M);
}