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
|
using namespace std;
#define maxn 100010
#define ll long long
int n;
struct {
int from, to, dist;
};
vector<int> G[maxn<<3];
vector<edge> edges;
int tot;
int ls[maxn<<3], rs[maxn<<3];
int _o;
int t1,t2;
ll deg[maxn<<3];
vector<ll> res;
bool vis[maxn<<3];
ll val[maxn<<3];
const ll inf = 1e18;
int pos[maxn];
void init(){
for(int i = 0; i <= 2 * n; i++)G[i].clear();
edges.clear();
}
void addedge(int from, int to, int dist){
edges.push_back(edge{from, to, dist});
tot = edges.size();
G[from].push_back(tot - 1);
deg[to]++;
}
struct node {
ll v;
int id;
bool operator<(const node &r)const{
return v > r.v;
}
}b[maxn];
void build(int &o, int l, int r){
o = ++_o;
if(l < r) {
int mid = l + r >> 1;
build(ls[o], l, mid);
build(rs[o], mid + 1, r);
addedge(ls[o], o, 0), addedge(rs[o], o, 0);
return;
}
val[o] = b[l].v;
pos[l] = o;
}
void update(int o, int tl, int tr, int l, int r, int x){
if(tr < l || r < tl)return;
if(l <= tl && r >= tr){
addedge(o, x, 0);
return;
}
int mid = tl + tr >> 1;
update(ls[o], tl, mid, l, r, x);
update(rs[o], mid + 1, tr, l, r, x);
}
priority_queue<node> q;
void insert(int o, int l, int r){
if(!deg[o]) {
q.push(node{val[o], o});
}
if(l == r)return;
int mid = l + r >> 1;
insert(ls[o], l, mid);
insert(rs[o], mid + 1, r);
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
init();
for(int i = 1; i <= n; i++){
cin >> b[i].v;
b[i].id = i;
}
build(t1, 1, n);
for(int i = 1; i <= n; i++){
int idd = b[i].id;
int u = b[i].v % n;
u++;
if(u == idd)continue;
if(u < idd){
update(t1, 1, n, u, idd - 1, pos[idd]);
}
else{
update(t1, 1, n, 1, idd - 1, pos[idd]);
update(t1, 1, n, u, n, pos[idd]);
}
}
insert(t1, 1, n);
while(!q.empty()){
node u = q.top();
q.pop();
if(vis[u.id])continue;
vis[u.id] = true;
if(u.v)
res.push_back(u.v);
for(int i = 0; i < G[u.id].size(); i++){
edge &e = edges[G[u.id][i]];
int v = e.to;
if(vis[v])continue;
deg[v]--;
if(!deg[v])q.push(node{val[v], v});
}
}
for(int i = 0; i < res.size(); i++){
cout << res[i] << (i == res.size() - 1 ? 'n' : ' ');
}
return 0;
}
|
近期评论