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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=1e5+5;
int n;
PII a[N];
struct Splay {
int rt,ch[N][2],sz[N],fa[N],mark[N];
PII val[N];
bool get(int x) {return x==ch[fa[x]][1];}
void clear(int x) {ch[x][0]=ch[x][1]=fa[x]=mark[x]=sz[x]=0;}
void push_up(int x) {sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}
void push_down(int x) {
if(mark[x]) {
mark[ch[x][0]]^=1;
mark[ch[x][1]]^=1;
mark[x]=0;
swap(ch[x][0],ch[x][1]);
}
}
void build(int l,int r,int f) {
int mid=l+r>>1;
val[mid]=a[mid];
if(f==-1) rt=mid;
else fa[mid]=f,ch[f][r>f]=mid,ch[mid][0]=ch[mid][1]=0;
if(l<mid) build(l,mid-1,mid);
if(r>mid) build(mid+1,r,mid);
push_up(mid);
}
void rotate(int x) {
int y=fa[x],z=fa[y];
push_down(y);
push_down(x);
int chk=get(x);
ch[y][chk]=ch[x][chk^1];
if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
ch[x][chk^1]=y;
fa[y]=x,fa[x]=z;
if(z) ch[z][y==ch[z][1]]=x;
push_up(y);
}
void splay(int x) {
push_down(x);
for(int f=fa[x];f=fa[x],f;rotate(x)) if(fa[f])
rotate(get(x)==get(f)?f:x);
push_up(x);
rt=x;
}
int pre() {
int cur=ch[rt][0];
push_down(cur);
while(ch[cur][1]) cur=ch[cur][1],push_down(cur);
splay(cur);
return cur;
}
void del() {
if(!ch[rt][0]&&!ch[rt][1]) {
clear(rt);
rt=0;
return;
}
else if(!ch[rt][0]) {
int cur=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(cur);
}
else if(!ch[rt][1]) {
int cur=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(cur);
}
else {
int cur=rt;
pre();
fa[ch[cur][1]]=rt;
ch[rt][1]=ch[cur][1];
clear(cur);
push_up(rt);
}
}
void reverse(int x,int t) {
splay(x);
mark[ch[rt][0]]^=1;
printf("%d%c",sz[ch[rt][0]]+t,t==n?'\n':' ');
del();
}
}splay;
bool cmp(PII a,PII b) {
return a.SE<b.SE||a.SE==b.SE&&a.FI<b.FI;
}
int main() {
while(~scanf("%d",&n)&&n) {
for(int i=1;i<=n;i++) {
int x;
cin>>x;
a[i]=MP(i,x);
}
splay.build(1,n,-1);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) splay.reverse(a[i].FI,i);
}
return 0;
}
|