本文共 2684 字，大约阅读时间需要 8 分钟。
题意：
给一系列数，执行一系列的反转操作，要求最后稳定排序这些数，并且输出每次反转的右边界。
题解：
怎么运用伸展树去解决呢？（反转操作。伸展树的基本操作）
对原始数据记录值和下标，然后按照值优先排序。伸展树存放下标。然后扫描一遍所有的数：
第一个数在x位置，把伸展树值为x的节点伸展到根，左子树size+1即为所求的右边界。然后把x左边的节点反转，删除根（x节点）。
顺次第二个数，第三个~
#includeusing namespace std;int n;const int maxn = 1e5+99;struct splaytree{ int pre[maxn],ch[maxn][2],sz[maxn],rev[maxn],root; void update(int r)///反转更新 { if(r == 0)return; rev[r]^=1;//下面的节点翻转抵消 swap(ch[r][0],ch[r][1]); } void pushdown(int r) { if(rev[r]) { update(ch[r][0]); update(ch[r][1]); rev[r] = 0; } } void pushup(int r) { sz[r] = 1 + sz[ch[r][0]] + sz[ch[r][1]]; } void rotate(int x,int d) { int y = pre[x]; pushdown(y); pushdown(x); ch[y][d^1] = ch[x][d]; pre[ch[x][d]] = y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x] = pre[y]; ch[x][d] = y; pre[y] = x; pushup(y); } void splay(int r,int goal) { pushdown(r); while(pre[r] != goal) { if(pre[pre[r]] == goal) rotate(r,ch[pre[r]][0]==r); else { int y = pre[r]; int d = ch[pre[y]][0]==y; if(ch[r][d]==r) { rotate(r,!d); rotate(r,d); } else { rotate(y,d); rotate(r,d); } } } pushup(r); if(goal == 0)root = r; } void newnode(int &r,int fa,int k) { r = k; pre[r] = fa; ch[r][0] = ch[r][1] =0; sz[r] = 1; } void build(int &x,int l,int r,int fa) { if(l>r)return; int m = (l+r)>>1; newnode(x,fa,m); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); pushup(x); } void init() { root = 0; ch[root][0] = ch[root][1] = rev[root] = sz[root] = pre[root] = 0; build(root,1,n,0); } int getmax(int r) { pushdown(r); while(ch[r][1]) { r = ch[r][1]; pushdown(r); } return r; } void remove()/**删根*/ { if(ch[root][0]==0) { root = ch[root][1]; pre[root] = 0; } else { int m = getmax(ch[root][0]); splay(m,root); ch[m][1] = ch[root][1]; pre[ch[root][1]] = m; root = m; pre[m] = 0; pushup(root); } }}st;struct node{ int num,id; bool operator < (const node& a)const { if(num == a.num)return id
转载地址：http://jbyci.baihongyu.com/