題目思路：splay，區間反轉。
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
#define M 101000
#define keytree ch[ch[root][1]][0]
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
struct node
{
int v,id;
bool operator<(const node a)const
{
if(v==a.v)
return id<a.id;
return v<a.v;
}
}a[101000];
int b[101000],n;
int p[M],ch[M][2],v[M],s[M],mi[M],rev[M];
int top1,root;
void visit(int x)
{
if(!x) return;
printf("x %d p %d ch0 %d ch1 %d v %d s %d mi %d co %d\n",x,p[x],ch[x][0],ch[x][1],v[x],s[x],mi[x],rev[x]);
visit(ch[x][0]);
visit(ch[x][1]);
}
void debug()
{
printf("debug\n");
visit(root);
}
void newnode(int &x,int val,int pre)
{
x=++top1;
ch[x][0]=ch[x][1]=rev[x]=0;
s[x]=1;
mi[x]=v[x]=val;
p[x]=pre;
}
void up(int x)
{
int l=ch[x][0],r=ch[x][1];
s[x]=1+s[l]+s[r];
mi[x]=min(mi[l],mi[r]);
mi[x]=min(mi[x],v[x]);
}
void down(int x)
{
if(!rev[x]) return;
int l=ch[x][0],r=ch[x][1];
if(l)
{
swap(ch[l][0],ch[l][1]);
rev[l]^=1;
}
if(r)
{
swap(ch[r][0],ch[r][1]);
rev[r]^=1;
}
rev[x]=0;
}
void build(int &x,int l,int r,int pre)
{
if(l>r) return;
int mid=(l+r)>>1;
newnode(x,b[mid],pre);
build(ch[x][0],l,mid-1,x);
build(ch[x][1],mid+1,r,x);
up(x);
}
void init()
{
top1=0;
v[0]=mi[0]=inf;
newnode(root,-inf,0);
newnode(ch[root][1],inf,root);
s[root]=2;
build(keytree,1,n,ch[root][1]);
up(ch[root][1]);
up(root);
}
void rot(int x,int f)
{
int y=p[x];
down(x),down(y);
p[ch[x][f]]=y;
ch[y][!f]=ch[x][f];
p[x]=p[y];
if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x;
p[y]=x;
ch[x][f]=y;
up(y);
}
void splay(int x,int goal)
{
while(p[x]!=goal)
{
if(p[p[x]]==goal) rot(x,ch[p[x]][0]==x);
else
{
int y=p[x],f=ch[p[y]][0]==y;
if(ch[y][f]==x)
rot(x,!f);
else
rot(y,f);
rot(x,f);
}
}
up(x);
if(!goal) root=x;
}
void rotto(int k,int goal)
{
int x=root;
down(x);
while(s[ch[x][0]]!=k)
{
if(s[ch[x][0]]>k)
x=ch[x][0];
else
{
k-=s[ch[x][0]]+1;
x=ch[x][1];
}
down(x);
}
splay(x,goal);
}
void getmin(int l,int r)
{
rotto(l-1,0);
rotto(r+1,root);
int x=keytree;
int num=1;
down(x);
while(v[x]!=l)
{
if(mi[ch[x][0]]==l)
x=ch[x][0];
else
{
num+=s[ch[x][0]]+1;
x=ch[x][1];
}
down(x);
}
num+=s[ch[x][0]];
rotto(l+num,root);
rev[keytree]=1;
swap(ch[keytree][0],ch[keytree][1]);
if(l==1)
printf("%d",l+num-1);
else
printf(" %d",l+num-1);
}
int main()
{
int i;
while(scanf("%d",&n),n)
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].v);
a[i].id=i;
}
sort(a+1,a+n+1);
for(i=1;i<=n;i++)
{
b[a[i].id]=i;
}
init();
for(i=1;i<=n;i++)
getmin(i,n);
puts("");
}
}
作者：Wings_of_Liberty
