但战斗还未结束（war）

xieyikai2333 · 2023-07-16 23:31:51 · 个人记录

但战斗还未结束（war） 题解

0x01 解题思路

不难发现，题目给出的信息可以转化为 f_i 之间的大小关系，之后建图拓扑排序，i 在拓扑序中的位置显然即 f_i 的一种合法的值。

0x02 具体过程

• 对于给定的 a 序列，我们构造 b 序列，b_x 表示 x 在序列 a 中的出现位置。特别地，对于未在 a 中出现的整数 x \in [1,n]，我们令 b_x=n+1；对于 a_i=-1，我们令 a_i \gets n+1。至于为何这样定义，阅读下文后显然可以理解。

• 考虑合法的排列 f 应该满足的条件：

  1. 首先，根据题意显然有 f_{a_i}>f_i，即 f_u>f_{b_u}（用 u 替换 a_i 可以转化）。
  2. 然后考虑题目中 “未标记” 这一点对于答案的限制。显然，若 j 满足 f_j>f_i 且 j<a_i，那么 j 一定在之前已经被标记过（即 b_j<i），不然 j 势必会取代现在的 a_i。也就是说：对于任意 j<a_i，若满足 f_j>f_i，则 b_j<i。根据“真命题的逆否命题也是真命题”，可以得出，对于任意 j<a_i，若满足 b_j\ge i，则 f_j \leq f_i。当然，等于号取到的情况显然不存在，所以：对于任意 j<a_i，若满足 b_j>i，则 f_j<f_i。

• 由于此时关系数达到了 \text{O}(n^2)，无法通过全部数据，我们考虑优化。使用 DFS 进行拓扑排序，此时，对于只有 n 条的关系 1，直接处理即可。对于关系 2，我们维护一颗线段树，记录区间最大 p_j，和 i 比较大小即可判断 i 和 j 是否满足关系 2。每访问一个结点，便将其从线段树中删去，这样每个结点最多被询问 1 次。至此，时间复杂度优化至 \Theta(n \log n)。

0x03 代码实现

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],b[N],f[N],mpos[N<<2],n,cnt=0;
bool vis[N];
int MAX(int x,int y){return b[x]>b[y]?x:y;}
void build(int p,int l,int r)
{
    if(l==r)return mpos[p]=l,void();
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    mpos[p]=MAX(mpos[p<<1],mpos[p<<1|1]);
    return;
}
void modify(int p,int l,int r,int x,int v)
{
    if(l==r)return b[x]=v,void();
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,v);
    else modify(p<<1|1,mid+1,r,x,v);
    mpos[p]=MAX(mpos[p<<1],mpos[p<<1|1]);
    return;
}
int query(int p,int l,int r,int x,int y)
{
    if(x>r||y<l)return 0;
    if(x<=l&&r<=y)return mpos[p];
    int mid=(l+r)>>1;
    int resL=query(p<<1,l,mid,x,y);
    int resR=query(p<<1|1,mid+1,r,x,y);
    return MAX(resL,resR);
}
void dfs(int u)
{
    vis[u]=true;
    int to=b[u];
    modify(1,1,n,u,0);
    if(to<=n&&!vis[to])dfs(to);
    while(true)
    {
        int v=query(1,1,n,1,a[u]-1);
        if(b[v]<=u)break;
        dfs(v);
    }
    f[u]=++cnt;
    return;
}
int main()
{
    freopen("war.in","r",stdin);
    freopen("war.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(~a[i])b[a[i]]=i;
        else a[i]=n+1;
    }
    for(int i=1;i<=n;i++)if(!b[i])b[i]=n+1;
    build(1,1,n);
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
    for(int i=1;i<=n;i++)printf("%d ",f[i]);
    return 0;
}