对于大神来说这题是水题。我搞这题花了快2天。
伸展树的优点有什么，就是树不管你怎么旋转序列是不会改变得，并且你要使区间反转，只要把第k大的点转到根结点，那么它的左子树就是要交换的区间[l,r)，然后交换左右
子树就可以了（中序），根结点的位置就是i+siz[ch[root][0]],i是处理完的结点个数，siz[ch[root][0]]就是左子树（需要旋转的个数）。 旋转可以用lazy思想标记，这样时间就为logn了。由于第k大的值已经处理完成,所以直接将根结点删除。
代码:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define key_value ch[ch[root][1]][0] using namespace std; const int MAXN = 100010; struct node { int id; int v; }a[MAXN]; int pre[MAXN],ch[MAXN][2],siz[MAXN],lazy[MAXN],tot1,root; int s[MAXN],tot2,n; bool cmp(node fa,node fb) { if(fa.v != fb.v) return fa.v < fb.v; return fa.id < fb.id; } void Treavel(int x) { if(x) { Treavel(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,lazy=%2d ",x,ch[x][0],ch[x][1],pre[x],siz[x],lazy[x]); Treavel(ch[x][1]); } } void debug() { printf("root:%d ",root); Treavel(root); } void Newnode(int &rt,int pa,int k) { rt = k; pre[rt] = pa; siz[rt] = 1; lazy[rt] = 0; ch[rt][0] = ch[rt][1] = 0; } void pushup(int rt) { siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1; } void pushdown(int rt) { if(lazy[rt]){ lazy[ch[rt][0]] ^= 1; lazy[ch[rt][1]] ^= 1; swap(ch[rt][0],ch[rt][1]); lazy[rt] = 0; } } void build(int &rt,int l,int r,int pa) { if(l > r){ return ; } int m = (l+r)/2; Newnode(rt,pa,m); build(ch[rt][0],l,m-1,rt); build(ch[rt][1],m+1,r,rt); pushup(rt); } void Init() { root = tot1 = tot2 = 0; ch[root][0] = ch[root][1] = siz[root] = lazy[root] = pre[root] = 0; build(root,1,n,0); pushup(root); } void Rotate(int rt,int kind) { pushdown(pre[rt]); pushdown(rt); int y = pre[rt]; ch[y][!kind] = ch[rt][kind]; pre[ch[rt][kind]] = y; if(pre[y]){ ch[pre[y]][ch[pre[y]][1]==y] = rt; } pre[rt] = pre[y]; ch[rt][kind] = y; pre[y] = rt; pushup(y); pushup(rt); } void splay(int rt,int goal) { pushdown(rt); while(pre[rt] != goal) { if(pre[pre[rt]] == goal){ pushdown(pre[rt]); pushdown(rt); Rotate(rt,ch[pre[rt]][0]==rt); } else { pushdown(pre[pre[rt]]); pushdown(pre[rt]); pushdown(rt); int y = pre[rt]; int kind = ch[pre[y]][0]==y; if(ch[y][kind] == rt){ Rotate(rt,!kind); Rotate(rt,kind); } else { Rotate(y,kind); Rotate(rt,kind); } } } pushup(rt); if(goal == 0) root = rt; } int Get_max(int rt) { pushdown(rt); while(ch[rt][1]){ rt = ch[rt][1]; pushdown(rt); } return rt; } void del(int root) { if(ch[root][0] == 0){ root = ch[root][1]; pre[root] = 0; } else { int t = Get_max(ch[root][0]); splay(t,root); ch[t][1] = ch[root][1]; pre[ch[root][1]] = t; root = t; pre[root] = 0; pushup(root); } } 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,cmp); Init(); for(i=1; i<=n; i++){ //cout<<"test1: "<<endl; splay(a[i].id,0); // debug(); lazy[ch[root][0]] ^= 1; printf("%d",i+siz[ch[root][0]]); if(i < n)printf(" "); else printf(" "); del(root); } } }