题解：P13296 [GCJ 2013 #2] Erdős–Szekeres

更差的阅读体验

---

Update on 2025/11/28：添加了 \(O(n \log n)\) 的做法。

---

注意到，

• 对于 \(j < i, A_j \ge A_i\)，则有 \(X_j > X_i\)。因为如果 \(X_j < X_i, A_i \ge A_j + 1\)，矛盾。
• 对于 \(j > i, B_j \ge B_i\)，则有 \(X_j > X_i\)。因为如果 \(X_j < X_i, B_i \ge B_j + 1\)，矛盾。
• \(X_i \ge \min \{X_j \space |\space A_j = A_i - 1, j < i\}\)，表示 \(A_i\) 是从前面的一个 \(j\) 转移过来。
  • 由于对于 \(j_1 < j_2 < \cdots < j_k, A_{j_1} = A_{j_2} = \cdots = A_{j_k}\)，有 \(X_{j_1} > X_{j_2} > \cdots > X_{j_k}\)，所以记 \(lst_i\) 表示最大的 \(j\) 使 \(A_j = A_i - 1, j < i\)，则 \(X_i > X_{lst_i}\)。
• \(X_i \ge \min\{X_j \space | \space B_j = B_i - 1, j>i\}\)，表示 \(B_i\) 从后面的一个 \(j\) 转移过来。
  • 由于对于 \(j_1 < j_2 < \cdots < j_k, B_{j_1} = B_{j_2} = \cdots = B_{j_k}\)，有 \(X_{j_1} < X_{j_2} < \cdots < X_{j_k}\)，所以记 \(nxt_i\) 表示最小的 \(j\) 使 \(B_j = B_i - 1, j > i\)，则 \(X_i > X_{nxt_i}\)。

从上面我们可以得到足量的关于 \(X\) 的大小关系。

接下来为了找到字典序最小的排列，我们从第一个位置开始填数。假设 \(sz_i\) 表示至少有多少个数字比 \(i\) 小。则我们就看一下当前没有被选过的第 \(sz_i\) 小的数字，填进去即可。

至于怎么求 \(sz\)，可以由上面的不等关系建有向边，从大的往小的连边，看一个点可以到达多少个点。

实际上实现的时候可以用把边反着连，然后用 bitset 维护有多少个点可以到达当前点。

然后这道题就做完了。复杂度 \(O(T n^2)\)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
int n,num,a[N],b[N],in[N],vis[N],fl[N],getans[N];
vector<int> G[N];
bitset<N> bt[N];
void solve(int Case)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),G[i].clear(),
        in[i]=vis[i]=getans[i]=0,bt[i].reset(),bt[i].set(i);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]>=a[j])G[j].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(b[i]<=b[j])G[i].push_back(j),in[j]++;
    for(int i=1;i<=n;i++)
        for(int j=i-1;j;j--)
            if(a[j]==a[i]-1){G[j].push_back(i),in[i]++;break;}
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(b[j]==b[i]-1){G[j].push_back(i),in[i]++;break;}
    queue<int> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    while(q.size())
    {
        int u=q.front(); q.pop();
        for(int v:G[u]){bt[v]|=bt[u];if(!--in[v])q.push(v);}
    }
    printf("Case #%d: ",Case);
    for(int i=1;i<=n;i++)
    {
        int sz=0;
        for(int j=1;j<=n;j++)
            if(bt[i][j]&&!getans[j])sz++;
        int j=0,cnt=0;
        while(cnt<sz)cnt+=!vis[++j];
        printf("%d%c",j," \n"[i==n]),vis[j]=getans[i]=1;
    }
}
main()
{
    int T,_=0; scanf("%lld",&T);
    while(T--)solve(++_); return 0;
}

---

到这里你可能会说，哥们你这个平方做法还是太菜了！别急，其实可以优化到 \(O(n \log n)\)。感谢 @STUDENT0 同学的帮助。

首先第一个瓶颈在于边数。我们把上面的四种情况从上往下标号为 \(1 \sim 4\)。显然第 \(3, 4\) 种边直接用一个桶就能记录。但其实我们发现，\(1, 2\) 种边可以削掉。

首先假如 \(j < i, A_j = A_i\)，那么 \(j\) 和 \(i\) 之间的边我们肯定要留住。但是由于有向边具有传递性，所以我们只需要向比 \(i\) 小且离得最近的 \(j\) 连边就可以了。

我们还要连 \(j < i, A_j > A_i\) 的边。由于我们有 \(3, 4\) 类边，也就是我们在相差为 \(1\) 的点对之间有连边。由于传递性，我们同样可以构造出任意两个差值之间的边。

所以对于 \(1, 2\) 类边，我们只需要找到最靠近的一个相等的位置连边。

第二个瓶颈在于求 DAG 上一个点可以到达的点数目。这个东西看起来不能低于 \(O(\frac{n^2}{\omega})\)，所以我们决定另辟蹊径。

我们考虑贪心，把大的数往后放是优的。所以我们可以看一下哪些数现在没有限制，然后取编号最大的，赋予最大的值。

所以我们可以由大的数向小的数连边，然后进行拓扑排序。取目前入度为 \(0\) 的点，扔到一个大根堆里面，然后取堆顶，将堆顶的位置赋为 \(n\)，然后把这个点删掉，下一个数赋值为 \(n-1\)，以此类推。

然后这道题就做完了，复杂度 \(O(T n \log n)\)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
int n,num,a[N],b[N],t[N],in[N],ans[N];
vector<int> G[N];
void solve(int Case)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),G[i].clear(),in[i]=t[i]=0;
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;t[a[i]]=i,i++)
        if(t[a[i]])G[t[a[i]]].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=n;i;t[b[i]]=i,i--)
        if(t[b[i]])G[t[b[i]]].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=1;i<=n;t[a[i]]=i,i++)
        if(t[a[i]-1])G[i].push_back(t[a[i]-1]),in[t[a[i]-1]]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=n;i;t[b[i]]=i,i--)
        if(t[b[i]-1])G[i].push_back(t[b[i]-1]),in[t[b[i]-1]]++;
    priority_queue<int> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    int now=n;
    while(q.size())
    {
        int u=q.top(); q.pop(),ans[u]=now--;
        for(int v:G[u])if(!--in[v])q.push(v);
    }
    printf("Case #%d: ",Case);
    for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);
}
main()
{
    int T,_=0; scanf("%d",&T);
    while(T--)solve(++_);
    return 0;
}