```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(time(0));
struct node{
int l;
int r;
int w;
int key;
int siz;
int minn;
bool flag;
}e[100010];
struct nodee{
int w;
int id;
}a[100010];
int tmp[100010];
int n,m;
int cnt,rt;
bool cmp(nodee x,nodee y){
if(x.w != y.w)return x.w < y.w;
else return x.id < y.id;
}
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].minn = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
e[i].minn = e[i].w;
if(e[i].l)e[i].minn = min(e[i].minn,e[e[i].l].minn);
if(e[i].r)e[i].minn = min(e[i].minn,e[e[i].r].minn);
}
void pushdown(int i){
swap(e[i].l,e[i].r);
if(e[i].l)e[e[i].l].flag ^= 1;
if(e[i].r)e[e[i].r].flag ^= 1;
e[i].flag = false;
}
void split(int i,int siz,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[i].flag)pushdown(i);
if(e[e[i].l].siz < siz){
x = i;
split(e[i].r,siz - e[e[i].l].siz - 1,e[i].r,y);
}
else {
y = i;
split(e[i].l,siz,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key < e[y].key){
if(e[x].flag)pushdown(x);
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
if(e[y].flag)pushdown(y);
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
int x,y,z;
void ins(int w){
split(rt,w,x,y);
rt = merge(merge(x,newnode(w)),y);
}
int getrk(int x){
int rk = 1;
while(1){
pushdown(x);
if(e[x].l && e[e[x].l].minn == e[x].minn)x = e[x].l;
else if(e[x].r && e[e[x].r].minn == e[x].minn){
rk += e[e[x].l].siz + 1;
x = e[x].r;
}
else return rk + e[e[x].l].siz;
}
}
signed main(){
cin>>n;
for(int i = 1;i <= n;i ++){
a[i].w = read();
a[i].id = i;
}
sort(a + 1,a + n + 1,cmp);
for(int i = 1;i <= n;i ++)tmp[a[i].id] = i;
for(int i = 1;i <= n;i ++)ins(tmp[i]);
for(int i = 1;i <= n;i ++){
int k = getrk(rt);
split(rt,k,x,y);
split(x,k - 1,x,z);
e[x].flag ^= 1;
rt = merge(x,y);
cout<<k + i - 1<<" ";
}
return 0;
}
```
by EDqwq @ 2021-03-02 12:53:20
这种题不是随便拉一份题解下来拍一下就好了啊。。。数据又不难造。。。数据结构题都有错误样例了也很好调了吧/jy
by Leap_Frog @ 2021-03-02 16:37:34