Wide Swap

Time Limit: 50 Sec Memory Limit: 512 MB

Description

img

Input

img

Output

img

Sample Input

8 3
　　4 5 7 8 3 1 2 6

Sample Output

1
　　2
　　6
　　7
　　5
　　3
　　4
　　8

HINT

img

Solution

首先，直接做难度系数较高，假设原序列为a，我们考虑设一个p，p[a_i] = i，即将题目中的权值与下标调换。

那么显然，要令a字典序最小，只要让p字典序最小即可。因为**“权值小的尽量前”与“前面的权值尽量小”**是一个意思。

现在操作转化为：相邻元素且权值差>=k的可以换顺序。

考虑一个暴力怎么做，显然是 i 与后面的所有 j 比，如果 abs(p_i - p_j) < k，则 i 和 j 的相对顺序就确定了， 连一条 p_i -> p_j 的边。

连边之后跑一边拓扑即可。

显然复杂度在于连边，因为这样暴力会有很多无用边。比如A->B, B->C, A->C，这条A->C显然无用。

我们考虑如何删掉 A->C 这种边。

倒着加入，显然 p_i 连向 (p_i-k, p_i)∪(p_i, p_i+k)。我们只需要分别连向两个区间中下标最小的那一个即可。用线段树维护一下区间最小值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

#define next nxt
const int ONE = 1000005;
const int INF = 2147483640;

int get()
{
    int res = 1, Q = 1; char c;
    while( (c = getchar()) < 48 || c > 57)
        if(c == '-') Q = -1;
    if(Q) res = c - 48;
    while( (c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res * Q;
}

int n, k;
int A[ONE], p[ONE];
int next[ONE], first[ONE], go[ONE], Input[ONE], tot;
priority_queue <int, vector <int>, greater <int> > q;

int res = INF;
namespace Seg
{
    struct power {int val;} Node[ONE * 4];
    void Build(int i, int l, int r)
    {
        Node[i].val = INF;
        if(l == r) return;
        int mid = l + r >> 1;
        Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r);
    }

    void Update(int i, int l, int r, int L, int x)
    {
        if(L <= l && r <= L)
        {
            Node[i].val = x;
            return;
        }
        int mid = l + r >> 1;
        if(L <= mid) Update(i << 1, l, mid, L, x);
        else Update(i << 1 | 1, mid + 1, r, L, x);
        Node[i].val = min(Node[i << 1].val, Node[i << 1 | 1].val);
    }

    void Query(int i, int l, int r, int L, int R)
    {
        if(L > R) return;
        if(L <= l && r <= R)
        {
            res = min(res, Node[i].val);
            return;
        }
        int mid = l + r >> 1;
        if(L <= mid) Query(i << 1, l, mid, L, R);
        if(mid + 1 <= R) Query(i << 1 | 1, mid + 1, r, L, R);
    }
}

void Add(int u, int v)
{
    Input[v]++, next[++tot] = first[u], first[u] = tot, go[tot] = v;
}

void Deal()
{
    int now = 0;
    for(int i = 1; i <= n; i++)
        if(!Input[i]) q.push(i);
    while(!q.empty())
    {
        int u = q.top(); q.pop();
        A[u] = ++now;
        for(int e = first[u]; e; e = next[e])
        {
            int v = go[e];
            if(--Input[v] == 0) q.push(v);
        }
    }
    for(int i = 1; i <= n; i++) printf("%d\n", A[i]);
}

int main()
{
    n = get(), k = get();
    for(int i = 1; i <= n; i++) p[get()] = i;

    Seg::Build(1, 1, n);
    for(int i = n; i >= 1; i--)
    {
        res = INF, Seg::Query(1, 1, n, p[i] + 1, min(p[i] + k - 1, n));
        if(res != INF) Add(p[i], p[res]);

        res = INF, Seg::Query(1, 1, n, max(1, p[i] - k + 1), p[i] - 1);
        if(res != INF) Add(p[i], p[res]);

        Seg::Update(1, 1, n, p[i], i);
    }

    Deal();
}