「BZOJ3506」[CQOI2014]排序机械臂

Description

SORT 公司是一个专门为人们提供排序服务的公司,该公司的宗旨是「顺序是最美丽的」。

为了把工厂中高低不等的物品按从低到高排好序,工程师发明了一种排序机械臂。

它遵循一个简单的排序规则,第一次操作找到高度最低的物品的位置 P1P_1,并把左起第一个物品至 P1P_1 间的物品(即区间 [1,P1][1,P_1] 间的物品)反序;第二次找到第二低的物品的位置 P2P_2,并把左起第二个至 P2P_2 间的物品(即区间 [2,P2][2,P_2] 间的物品)反序……最终所有的物品都会被排好序。

上图给出有六个物品的示例,第一次操作前,高度最低的物品在位置 44,于是把第一至第四的物品反序;第二次操作前,第二低的物品在位罝六,于是把第二至六的物品反序……

你的任务便是编写一个程序,确定一个操作序列,即每次操作前第 ii 低的物品所在位置 PiP_i,以便机械臂工作。需要注意的是,如果有高度相同的物品,必须保证排序后它们的相对位置关系与初始时相同。

Input

输入共两行,第一行为一个整数 NNNN 表示物品的个数。
第二行为 NN 个用空格隔开的正整数,表示 NN 个物品最初排列的编号

Output

输出共一行,NN 个用空格隔开的正整数 P1,P2,P3,,PnP_1,P_2,P_3,\ldots,P_nPiP_i 表示第 ii 次操作前第 ii 小的物品所在的位置。

注意:如果第 ii 次操作前,第 ii 小的物品己经在正确的位置 PiP_i 上,我们将区间 [Pi,Pi][P_i,P_i] 反转 (单个物品)。

Sample Input

1
2
6
3 4 5 1 6 2

Sample Output

1
4 6 4 5 6 6

HINT

对于所有的数据,1N1000001 \leq N \leq 100000

Solution

splay区间翻转。
注意先翻转l1l-1,然后把rr翻转到l1l-1的右儿子上。
splaysplay操作的时候记得downdown
编号可能会重复,需要自行修改他们的编号。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 101000;
int n, a[N];
int ch[N][2], fa[N], r[N];
#define rt ch[0][1]
int siz[N];
void up(int x) {
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void down(int x) {
if(r[x]) {
r[ch[x][0]] ^= 1;
r[ch[x][1]] ^= 1;
r[x] = 0;
swap(ch[x][0], ch[x][1]);
}
}
int build(int l, int r, int F) {
int mid = (l + r) >> 1;
int x = a[mid];
fa[x] = F;
if(l < mid)ch[x][0] = build(l, mid - 1, x);
if(r > mid)ch[x][1] = build(mid + 1, r, x);
up(x);
return x;
}
bool ident(int x) {return ch[fa[x]][1] == x;}
void con(int x, int F, int how) {ch[F][how] = x, fa[x] = F;}
void rotate(int x) {
if(ident(x)) {
int y = fa[x];
int z = ch[x][0];
con(x, fa[y], ident(y));
con(z, y, 1);
con(y, x, 0);up(y);up(x);
} else {
int y = fa[x];
int z = ch[x][1];
con(x, fa[y], ident(y));
con(z, y, 0);
con(y, x, 1);up(y);up(x);
}
}
int st[N], top;
void splay(int x, int to) {
int y = x;
top = 0;
while(y != to) st[++top] = y, y = fa[y];
while(top) down(st[top--]);
to = fa[to];
for(y = fa[x]; y != to; y = fa[x]) {
if(fa[y] == to) rotate(x);
else {
if(ident(x) == ident(y)) rotate(y), rotate(x);
else rotate(x);
}
}
}
int find(int val) {
int x = rt;
while(x) {
down(x);
if(siz[ch[x][0]] + 1 == val) return x;
if(siz[ch[x][0]] >= val) x = ch[x][0];
else val -= siz[ch[x][0]] + 1, x = ch[x][1];
}
return -1;
}
void print(int x) {
down(x);
if(ch[x][0]) print(ch[x][0]);
printf("%d ", x-1);
if(ch[x][1]) print(ch[x][1]);
}
void change(int x, int y) {
x = find(x);
y = find(y);
splay(x, rt);
splay(y, ch[x][1]);
r[ch[y][0]] ^= 1;
}
int id[N];
bool cmp(int x, int y) {
if(a[x] == a[y]) return x < y;
return a[x] < a[y];
}
int main() {
n = read();
for(int i = 1; i <= n; ++i)
a[i] = read(), id[i] = i;
sort(id + 1, id + 1 + n, cmp);
for(int i = 1; i <= n; ++i)
a[id[i]] = i + 1;
a[0] = 1;
a[n + 1] = n + 2;
rt = build(0, n + 1, 0);
for(int i = 2; i <= n + 1; ++i) {
splay(i, rt);
printf("%d ", siz[ch[i][0]]);
if(siz[ch[i][0]] + 2 > n + 2) exit(0);
change(i-1, siz[ch[i][0]] + 2);
}
return 0;
}