AT1984 AGC001F Wide Swap 题解【拓扑排序】【线段树】【排列组合】

点击量：232

    排列的转化以及拓扑排序的建模加线段树优化连边。

目录

Problem Statement

You are given a permutation \(P_1\dots P_N\) of the set \(\{1, 2,\dots , N\}\).

You can apply the following operation to this permutation, any number of times (possibly zero):

Choose two indices \(i,j(1\le i<j\le N)\), such that \(j−i\ge K\) and \(|P_i−P_j|=1\). Then, swap the values of \(P_i\) and \(P_j\).

Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

Constraints

\[2\le N\le 500,000
1\le K\le N−1\]
\(P\) is a permutation of the set \(\{1, 2, …, N\}\).

---

Input

The input is given from Standard Input in the following format:

N K
P1 P2 … PN

Output

Print the lexicographically smallest permutation that can be obtained.

---

Samples

Sample Input 1

4 2
4 2 3 1

Sample Output 1

2
1
4
3

One possible way to obtain the lexicographically smallest permutation is shown below:

4231
4132
3142
2143

Sample Input 2

5 1
5 4 3 2 1

Sample Output 2

1
2
3
4
5

Sample Input 3

8 3
4 5 7 8 3 1 2 6

Sample Output 3

1
2
6
7
5
3
4
8

题意：

    给定\(N\)和\(K\)和一个\(1\sim N\)的排列\(P\)，两个位置的数字\(P_i,P_j\)允许交换当且仅当\(|P_i-P_j|=1\)且\(|i-j|\ge K\)。问能得到的最小字典序是多少。

题解：

    如果我们直接贪心，我们是不知道是否存在提前交换后面的元素可以造成更优解的，因此最暴力的算法只能是\(O(n^n)\)的搜索。但是遇到排列问题会有一种转化思路，就是把原排列数组转化为位置数组，也就是\(b_i\)表示\(i\)在\(a\)数组（即原数组）中的位置。

    对于样例1，我们可以得到\(\{4,2,3,1\}\)（为什么和原数组一样啊），此时可以发现我们的约束条件变得具体了：\(|P_i-P_j|=1\)在这里就是两数相邻的意思，\(|i-j|\ge K\)即\(b\)数组中两数之差大于等于\(K\)。结合起来表示在\(b\)数组中两数相邻且差大于等于\(K\)。

    那么当两数不能交换，就是当即使两数相邻，他们两个的差小于\(K\)，也不能交换，也就是说，只要满足两数之差小于\(K\)，无论位置关系如何，都不能交换。分析这个数组\(\{4,2,3,1\}\)，对于\(4\)这个数字而言，它与后面的\(3,1\)两个数字都无法交换，因此在这个数组中\(4\)一定在\(3\)前面，\(4\)也一定在\(1\)前面。

    我们把一个数组分析完后可以发现，这样的关系构成了一个DAG。DAG,DAG…当然是想拓扑排序了！但是拓扑排序有什么用呢？我们回过头来想想\(b\)这个数组的意义，\(b_i\)表示\(i\)这个数在原序列中的位置，如果\(b_i\)和\(b_j\)不可交换，那么\(b_i\)的位置上数一定比\(b_j\)位置上的数要小，那么连有向边\(a\rightarrow b\)的意义就是\(a\)处的数一定小于\(b\)处的数。然后我们进行优先队列拓扑排序就可以让字典序最小了（每次取出可行的最小数）。

    但是上面连的边数可能达到\(O(n^2)\)，而在拓扑排序中，如果\(a\rightarrow b,b\rightarrow c,a\rightarrow c\)，那么对于\(c\)限制最大的是\(b\)，因为\(b\)的深度要深一些，因此\(a\rightarrow c\)这条边就可以不需要了，也就是说，每个点只连接深度尽可能浅的合法点；深度尽可能浅，即在数组的位置最靠前，那么我们可以用线段树来维护区间内下标最小的元素是哪个。但是要注意，合法的区间有两个，分别是\((P_i-K,P_i-1)\)和\((P_i+1,P_i+K)\)，它们两个不一定互相影响，因此可以连出两条边。又因为我们只连接后面的边，所以我们要倒序枚举插入线段树。

    技巧比较多，时间复杂度为\(O(n\log n)\)。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3fffffff
using std::min;
struct node
{
    int l,r,v;//维护区间最小值
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=inf;
    }
    node()
    {
        v=inf;
    }
}t[2010000];
void build(int k,int l,int r)
{
    t[k]=node(l,r);
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void change(int k,int p,int x)
{
    if(t[k].l==t[k].r)
    {
        t[k].v=x;
        return;
    }
    int mid=(t[k].l+t[k].r)>>1;
    if(p<=mid)
        change(ls,p,x);
    else
        change(rs,p,x);
    t[k].v=min(t[ls].v,t[rs].v);
}
int ask(int k,int l,int r)
{
    if(r<t[k].l||l>t[k].r)
        return inf;
    if(l<=t[k].l&&r>=t[k].r)
        return t[k].v;
    return min(ask(ls,l,r),ask(rs,l,r));
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge(){}
}e[1010000];
int in[1010000],head[1010000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    ++in[to];
}
int a[500500],b[500500];
int heap[500500],l=0;
void Push(int x)
{
    heap[++l]=x;
    int i=l;
    while(i>1&&heap[i]<heap[i>>1])
    {
        int tmp=heap[i];
        heap[i]=heap[i>>1];
        heap[i>>1]=tmp;
        i>>=1;
    }
}
void pop()
{
    heap[1]=heap[l--];
    int i=1;
    while(i<<1<=l&&(heap[i]>heap[i<<1]||heap[i]>heap[i<<1|1]))
    {
        if(heap[i<<1]<heap[i<<1|1]||i<<1==l)
        {
            int tmp=heap[i];
            heap[i]=heap[i<<1];
            heap[i<<1]=tmp;
            i<<=1;
        }
        else
        {
            int tmp=heap[i];
            heap[i]=heap[i<<1|1];
            heap[i<<1|1]=tmp;
            i=i<<1|1;
        }
    }
}
int ans[500500],cnt=0;
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        a[u]=i;
    }
    for(int i=n;i;--i)
    {
        int tmp=ask(1,a[i]+1,a[i]+m-1);
        if(tmp!=inf)
            add(a[i],a[tmp]);
        tmp=ask(1,a[i]-m+1,a[i]-1);
        if(tmp!=inf)
            add(a[i],a[tmp]);
        change(1,a[i],i);
    }
    for(int i=1;i<=n;++i)
        if(!in[i])
            Push(i);
    while(l)
    {
        int x=heap[1];
        ans[x]=++cnt;
        pop();
        for(int i=head[x];~i;i=e[i].nxt)
        {
            --in[e[i].n];
            if(!in[e[i].n])
                Push(e[i].n);
        }
    }
    for(int i=1;i<=n;++i)
        printf("%d\n",ans[i]);
    return 0;
}