Young Maids

Time Limit: 50 Sec Memory Limit: 512 MB

Description

给定一个排列，每次选出相邻的两个放在队头，要求字典序最小。

Input

第一行一个整数n，第二行n个数表示这个排列。

Output

n个数表示答案。

Sample Input

8
　　4 6 3 2 8 5 7 1

Sample Output

3 1 2 7 4 6 8 5

HINT

n%2=0，2 <= n <= 2e5

Solution

倒着考虑。
　　我们维护一个小根堆，堆里面存**[l, r, val]，表示在区间[l, r]中选择两个元素，第一个元素A的权值为val**（保证合法），以val为第一关键字。

那么显然，我们每次选出堆顶进行操作。

显然，若我们取走了A,B（pos[A] < pos[B]），[l,r]就被拆成了 [l,A-1], [A+1,B-1], [B+1,r]，我们要保证每一个区间长度都是偶数。
　　那么只要有，pos[A]%2 == pos[l]%2，pos[B]%2 == pos[r]%2。
　　又由于我们每次减少两个数，所以这样显然可以保证 pos[B]-pos[A]+1 % 2 == 0。

现在问题就是怎么求出A、B具体是那两个数，显然写个线段树维护一下 某段区间内奇数/偶数位置的min_val和所在的pos即可。

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
106
107
108
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 200005;
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;
int a[ONE];

struct point
{
    int id, val;
    friend bool operator <(point a, point b)
    {
        if(a.val != b.val) return a.val < b.val;
        return a.id < b.id;
    }
};
point res;

namespace Seg
{
    struct power {point odd, eve;} Node[ONE * 4];

    void Build(int i, int l, int r)
    {
        Node[i].odd.val = Node[i].eve.val = INF;
        if(l == r)
        {
            if(l & 1) Node[i].odd = (point){l, a[l]};
            else Node[i].eve = (point){l, a[l]};
            return;
        }
        int mid = l + r >> 1;
        Build(i << 1, l, mid), Build(i << 1 | 1, mid + 1, r);
        Node[i].odd = min(Node[i << 1].odd, Node[i << 1 | 1].odd);
        Node[i].eve = min(Node[i << 1].eve, Node[i << 1 | 1].eve);
    }

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

struct power
{
    int l, r, val;
    bool operator <(power a) const
    {
        if(a.val != val) return a.val < val;
        return a.l < l;
    }
};
priority_queue <power> q;

point Get(int l, int r, int opt)
{
    res = (point){n + 1, INF};
    Seg::Query(1, 1, n, l, r, opt);
    return res;
}

void Add(int l, int r)
{
    if(l > r) return;
    q.push((power){l, r, Get(l, r, l % 2).val});
}

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

    Seg::Build(1, 1, n);
    Add(1, n);

    for(int i = 1; i <= n / 2; i++)
    {
        power u = q.top(); q.pop();
        point A = Get(u.l, u.r - 1, u.l % 2);
        point B = Get(A.id + 1, u.r, u.r % 2);
        printf("%d %d ", A.val, B.val);

        Add(u.l, A.id - 1), Add(A.id + 1, B.id - 1), Add(B.id + 1, u.r);
    }
}