AtCoder Grand Contest 001F Wide Swap

解法参考这位大佬的：https://www.cnblogs.com/BearChild/p/7895719.html

因为原来的数组不好做于是我们想反过来数组，根据交换条件：值相邻且位置差大于等于k，那么在变换后的数组就变成了位置相邻且差值大于等于k。这样的话变换操作变成了，相邻的大于等于k的值临近交换，于是我们注意到因为现在只能临近交换的原因，两个差值小于k的数他们的相对位置不可能发生改变。那么问题就变成了，在只有一些相对位置限制条件下，无限制的可以随意交换位置，求这个数组的最小字典序（原数组字典序最小也是现在数组字典序最小）。那么我们容易想到拓扑排序。

但是如果每个点都想后面差值小于k的点连边的话，这个图会变得十分巨大，时间无法承受。于是我们必循得考虑优化建图：我们注意到像a->b,b->c,a->c这种建图，a->c这条边是不必要的。于是我们想办法避免掉这种无意义的边，所以对于某个点，我们让它向后面的所有限制(即差值小于k)中只向最小的那一个点连边，那么用线段树维护这样的信息，这样就达到优化建图的目的。

这样只向最小的连边为什么是对的呢？借用上面大佬的一句话：倒着加入，显然 p_i 连向 (p_i-k, p_i)∪(p_i, p_i+k)。我们只需要分别连向两个区间中下标最小的那一个即可。

#include<bits/stdc++.h>

using namespace std;

const int N=5e5+;

const int INF=0x3f3f3f3f;

int n,k,tot,a[N],pos[N],deg[N],ans[N];

set<int> L,R;

vector<int> G[N];

priority_queue<int> q;

void toposort() {

    for (int i=;i<=n;i++)

        if (deg[i]==) q.push(-i);

    while (!q.empty()) {

        int x=-q.top(); q.pop();

        a[++tot]=x;

        for (int i=;i<G[x].size();i++) {

            int y=G[x][i];

            if (--deg[y]==) q.push(-y);

        }

    }

}

int Min[N<<];

void build(int rt,int l,int r) {

    Min[rt]=INF;

    if (l==r) return;

    int mid=l+r>>;

    build(rt<<,l,mid); build(rt<<|,mid+,r);

}

void update(int rt,int l,int r,int q,int v) {

    if (l==r) { Min[rt]=min(Min[rt],v); return; }

    int mid=l+r>>;

    if (q<=mid) update(rt<<,l,mid,q,v);

    if (q>mid) update(rt<<|,mid+,r,q,v);

    Min[rt]=min(Min[rt<<],Min[rt<<|]);

}

int query(int rt,int l,int r,int ql,int qr) {

    if (ql<=l && r<=qr) return Min[rt];

    int mid=l+r>>;

    int ret=INF;

    if (ql<=mid) ret=min(ret,query(rt<<,l,mid,ql,qr));

    if (qr>mid) ret=min(ret,query(rt<<|,mid+,r,ql,qr));

    return ret;

}

int main()

{

    cin>>n>>k;

    for (int i=;i<=n;i++) scanf("%d",&a[i]);

    for (int i=;i<=n;i++) pos[a[i]]=i;

    build(,,n);

    for (int i=n;i;i--) {

        int t1=query(,,n,max(,pos[i]-k+),pos[i]);

        if (t1<=n) G[pos[i]].push_back(pos[t1]),deg[pos[t1]]++;

        int t2=query(,,n,pos[i],min(n,pos[i]+k-));

        if (t2<=n) G[pos[i]].push_back(pos[t2]),deg[pos[t2]]++;

        update(,,n,pos[i],i);

    }

    toposort();

    for (int i=;i<=n;i++) ans[a[i]]=i;  //最后记得把答案反过来

    for (int i=;i<=n;i++) printf("%d\n",ans[i]);

    return ;

}

巴特西

AtCoder Grand Contest 001F Wide Swap

最新文章

热门文章