题解：P17505 [ICPC 2026 Wuhan I] Iroha and the Kingdom of Construction

· · 题解

好题啊！！！

下面介绍 zt17 学长放到模拟赛 sol 里的的（非卡常）做法。

记 L_i 为 i 第一次出现的位置，R_i 为 i 第二次出现的位置。

首先思考暴力怎么做。

:::info[策略 1 使用 n+1 个栈的确定性策略]{open}

考虑将 L_i 丢到 1 号栈中，R_i 丢到第 i+1 号栈中。

显然构造完成后 1 号栈内的所有元素都可以和 2\sim n+1 号栈中的一个栈进行操作。

:::

但是这个策略太浪费了，可以尝试去优化它。

具体地，我们有两种 2\sqrt{n} 的策略：

:::info[策略 2.1 期望使用 2\sqrt{n}+1 个栈的策略]{open}

注意到部分 R 可以共用一个栈。对于所有满足 L_x<L_y,R_x<R_y 的元素，我们可以将 R_x 和 R_y 放到一个栈中，此时会先消掉 y 再消掉 x，因此可以共用。

考虑按照 L_i 从小到大排序后不断尝试进行共用。不难发现最终每个栈内的 R_i 从下往上单调递增。也就是说，我们将 R_i 划分为了若干个递增子序列，而又根据 Dilworth 定理，划分的组数为整个 R 序列的 LDS 的长度。而 LDS 长度的期望是 2\sqrt{n} 的[^1]。

划分的过程就相当于是做导弹拦截。

:::

:::info[策略 2.2 使用 2\sqrt{n} 个栈的确定性策略]{open}

考虑分块，我们按照 R_i 从大到小排序，每 B 个元素为一组。我们开 \frac{n}{B} 个 A 类栈和 B 个 B 类栈。

对于第 i 个块，我们将这个块中的所有的 L 都放到第 i 个 A 类栈中，把这个块中的所有的 R 放到所有 B 类栈中并执行「策略 1」的构造。

构造完成后，我们先把第 \frac{n}{B} 个 A 类栈的所有元素拿去和 B 类栈的第一层匹配，再将第 \frac{n}{B}-1 个 A 类栈的所有元素拿去和 B 类栈的第二层匹配，以此类推，直到全部匹配完成。最终显然可以匹配完所有元素。

此时共需要 B+\frac{n}{B} 个栈，取 B=\sqrt{n} 得到最优块数 2\sqrt{n}。

:::

可惜 2\sqrt{n} 还是不够。

但是聪明的你发现，「策略 2.1」是对「策略 1」的直接优化，而你只需要把「策略 2.2」中的提到的「策略 1」修改为「策略 2.1」就可以进一步压缩空间！

:::success[策略 3 期望使用 3n^{\frac{1}{3}} 个栈的策略]{open}

考虑在「策略 2.2」的基础上进行改进。

仍然沿用「策略 2.2」的分块思想，但是将「策略 2.2」中每个块的构造过程变为「策略 2.1」。

此时期望使用 \frac{n}{B}+2\sqrt{B} 个栈，解得 B=n^{\frac{2}{3}} 时原式最小，为 3n^{\frac{1}{3}}。

:::

此时我们大约只会使用 238 个栈，于是做完了！

/*
blksz：块的大小
blknum：块的数量

在实现中，我们使用 1~blknum 号栈作为 A 类栈，blknum+1 号栈以后的栈为 B 类栈
*/
#include<bits/stdc++.h>
using namespace std;
#define homo_number 114514
// #define mod 998244353
//#define mod 1000000007
#define int long long
int n,sd,a[1000005],b[1000005];
set<pair<int,int>> s;
vector<int> v;
struct pp
{
    int l,r;
};
pp p[500005];
bool cmp1(pp x,pp y)
{
    return x.r>y.r;
}
bool cmp2(pp x,pp y)
{
    return x.l<y.l;
}
int blksz,blknum,belong[500005];
int tag[5005],sum[5005],st[5005],ed[5005],sz[5005];
void build()//2.2 分块
{
    blksz=pow(n,2.0/3.0);
    for(int i = 1;; i++)
    {
        st[i]=(i-1)*blksz+1;
        ed[i]=i*blksz;
        if(ed[i]>=n)
        {
            ed[i]=n;
            blknum=i;
            break;
        }
    }
    for(int i = 1; i <= blknum; i++)
    {
        for(int j = st[i]; j <= ed[i]; j++)
        {
            belong[j]=i;
        }
        sz[i]=ed[i]-st[i]+1;
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1; i <= 2*n; i++) cin>>a[i];
    for(int i = 1; i <= 2*n; i++)
    {
        if(p[a[i]].l==0) p[a[i]].l=i;
        else p[a[i]].r=i;
    }
    sort(p+1,p+n+1,cmp1);
    build();//构造 2.2 的分块
    for(int i = 1; i <= blknum; i++)
    {
        //对于 2.2 的每一个块，尝试执行 2.1 的策略
        for(int j = st[i]; j <= ed[i]; j++)
        {
            b[p[j].l]=i;
        }
        sort(p+st[i]+1,p+ed[i]+1,cmp2);
        s.clear();
        int nowcnt=blknum;
        for(int j = st[i]; j <= ed[i]; j++)
        {
            auto it=s.lower_bound(make_pair(p[j].r,0));
            if(it==s.begin())
            {
                nowcnt++;
                b[p[j].r]=nowcnt;
                s.insert(make_pair(p[j].r,nowcnt));
            }
            else
            {
                it--;
                b[p[j].r]=(*it).second;
                s.erase(it);
                s.insert(make_pair(p[j].r,b[p[j].r]));
            }
        }
    }
    for(int i = 1; i <= 2*n; i++) cout<<b[i]<<' ';
    return 0;
}

[^1]: 严格来说，随机排列下 LDS 的期望为 2\sqrt{n}+\alpha n^{\frac{1}{6}}+o(n^\frac{1}{6})。其中 \alpha 为 Tracy-Widom GUE 分布的均值，\alpha \approx -1.771\ 086\ 807\ 411。