AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=1552
【分析】
这题哇！又有翻转操作...每次要输出第几个？是吧...
所以又要用Splay了。
可是这道题有创新的地方，因为又有数值上的有序[取最小值]，又有位置上的有序[翻转和求第几个]
可是毕竟最小值的操作会简单很多...所以我们采用的是将位置作为Splay的节点信息。
那么怎么快速得到最小值的位置呢？当然就是常用的push_up了...向上更新就好了。
这里一定要注意题目所说：按照刚开始给你的顺序排序，在实现中就是数组的下标了，每次还需要比较两边最优值的大小和下标。
然后每次选出最小值，将其转到树根，输出其左子树的大小＋已经删去的最小值数目，然后将它删去，从左子树中选一个最右边的节点翻到顶上，作为新的节点。
大致过程就是这样啦...【表示都是笔者想出来的...很开心啊...只是速度还是没有某人快啊...】
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; inline int in(){
int x=,f=;char ch=getchar();
while((ch>'' || ch<'') && ch!='-') ch=getchar();
if(ch=='-') f=-,ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return x*f;
} const int maxn=;
const int INF=0x7f7f7f7f; struct Node{
int ch[],f;
int sz,mn,lc,dt;
bool rv;
}s[maxn]; int n,rt;
int a[maxn]; void push_down(int x){
if(s[x].rv){
swap(s[x].ch[],s[x].ch[]);
s[s[x].ch[]].rv^=,s[s[x].ch[]].rv^=;
s[x].rv=;
}
}
void update(int x){
s[x].sz=s[s[x].ch[]].sz+s[s[x].ch[]].sz+;
s[x].mn=s[x].dt,s[x].lc=x;
int l,r;l=s[x].ch[],r=s[x].ch[];
if((s[l].mn<s[x].mn) || (s[l].mn==s[x].mn && s[l].lc<s[x].lc)) s[x].mn=s[l].mn,s[x].lc=s[l].lc;
if((s[r].mn<s[x].mn) || (s[r].mn==s[x].mn && s[r].lc<s[x].lc)) s[x].mn=s[r].mn,s[x].lc=s[r].lc;
} int build(int l,int r){
if(l>r) return ;
int mid=(l+r)>>;
s[mid].ch[]=build(l,mid-);
s[mid].ch[]=build(mid+,r);
if(s[mid].ch[]) s[s[mid].ch[]].f=mid;
if(s[mid].ch[]) s[s[mid].ch[]].f=mid;
s[mid].dt=a[mid];
update(mid);
return mid;
} void Rotate(int x,int k){
int y=s[x].f;s[x].f=s[y].f;
if(s[y].f) s[s[y].f].ch[y==s[s[y].f].ch[]]=x;
s[y].ch[k]=s[x].ch[k^];
if(s[x].ch[k^]) s[s[x].ch[k^]].f=y;
s[y].f=x,s[x].ch[k^]=y;
update(y),update(x);
} void Splay(int x,int gf){
int y;
while(s[x].f!=gf){
y=s[x].f;
if(s[y].f==gf) Rotate(x,x==s[y].ch[]);
else{
int z=s[y].f;
if(y==s[z].ch[]){
if(x==s[y].ch[]) Rotate(y,),Rotate(x,);else Rotate(x,),Rotate(x,);}
else{
if(x==s[y].ch[]) Rotate(y,),Rotate(x,);else Rotate(x,),Rotate(x,);}
}
}
if(!gf) rt=x;
} int Find_right(int x){
int p=x,f=-;
while(p){
push_down(p);
f=p;p=s[f].ch[];
}
return f;
} int st[maxn],tp; void up_push_down(int x){
int p=x;
while(p)
st[++tp]=p,p=s[p].f;
while(tp)
push_down(st[tp--]);
} int main(){
#ifndef ONLINE_JUDGE
freopen("1552.in","r",stdin);
freopen("1552.out","w",stdout);
#endif n=in();
for(int i=;i<=n;i++) a[i]=in();
s[].mn=INF;s[].lc=-;
rt=build(,n);
int x;
for(int i=;i<=n;i++){
up_push_down(s[rt].lc);
Splay(s[rt].lc,);
printf("%d",s[s[rt].ch[]].sz+i);
if(i!=n) printf(" ");
s[s[rt].ch[]].rv^=;
if(!s[rt].ch[]){
s[s[rt].ch[]].f=;rt=s[rt].ch[];
}
else{
x=Find_right(s[rt].ch[]);
Splay(x,rt);
s[x].f=;
s[x].ch[]=s[rt].ch[];
if(s[rt].ch[])
s[s[rt].ch[]].f=x;
update(x);rt=x;
}
}
return ;
}