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

作者: wjyyy 分类: 拓扑排序,线段树,组合数学,解题报告 发布时间: 2018-10-26 10:58

点击量:62

 

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

 

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 P2PN

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;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Dew Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Dew
游客
Dew

%%%%%%

/* */