查最小值，删除，翻转。。。
显然splay啊。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 200005
#define inf 0x3f3f3f3f
using namespace std;
int n;
int ch[N][], fa[N];
int a[N];
int mn[N],zhi[N],size[N];
void push_up(int x)
{
size[x] = size[ch[x][]] + size[ch[x][]] + ;
mn[x] = min(zhi[x], min(mn[ch[x][]], mn[ch[x][]])); return;
}
int rev[N];
void push_down(int x)
{
if (rev[x])
{
rev[x] ^= ; rev[ch[x][]] ^= ; rev[ch[x][]] ^= ;
swap(ch[x][], ch[x][]);
}
return;
}
void rotate(int p)
{
int q = fa[p], y = fa[q], x = (ch[q][] == p);
ch[q][x] = ch[p][x ^ ]; fa[ch[q][x]] = q;
ch[p][x ^ ] = q; fa[q] = p;
fa[p] = y;
if (y)
{
if (ch[y][] == q)ch[y][] = p;
else ch[y][] = p;
}
push_up(q); return;
}
int root;
void splay(int x,int yy)
{
for (int y; y = fa[x]; rotate(x))
{
if (y == yy)break;
if (fa[y] != yy)
{
if ((ch[fa[y]][] == y) ^ (ch[y][] == x))rotate(x);
else rotate(y);
}
}
push_up(x);
if (!yy)root = x;
}
int cnt;
int find(int k, int x)
{
push_down(k);
if (mn[ch[k][]] == x)
{
return find(ch[k][], x);
}
if (zhi[k] == x)return size[ch[k][]] + ;
return find(ch[k][], x) + size[ch[k][]] + ;
}
int fd(int k, int x)
{
push_down(k);
if (size[ch[k][]] + == x)return k;
if (size[ch[k][]] + >= x)return fd(ch[k][],x);
return fd(ch[k][], x - size[ch[k][]] - );
}
struct node
{
int yuan,z;
friend bool operator < (node aa,node bb)
{
if(aa.z!=bb.z)return aa.z<bb.z;
return aa.yuan<bb.yuan;
}
}s[N];
int yin[N];
int main()
{
scanf("%d", &n); mn[] = inf;
for (int i = ; i <= n; i++)
{
s[i].yuan=i;scanf("%d",&s[i].z);
}
sort(s+,s+n+);
for(int i=;i<=n;i++)
{
a[s[i].yuan]=i;
}
root = ; a[n + ] = inf;
ch[][] = ; zhi[] = a[]; size[] = n + ;
for (int i = ; i <= n + ; i++)
{
size[i] = n - i + ;
zhi[i] = a[i]; fa[i] = i - ; ch[i - ][] = i;
}
for (int i = n + ; i >= ; i--)push_up(i);
splay(n, );
for (int i = ; i <= n; i++)
{
int y = find(root, mn[root]);
if(i!=n)printf("%d ",y+(i-));
else printf("%d",y+(i-));
int t = fd(root, y+);
splay(t, );
rev[ch[t][]] ^= ;
t = fd(root, );
splay(t, );
ch[t][] = ;
push_up(t);
}
puts("");
return ;
}