文艺平衡树

问题描述:

写一种数据结构，用来维护一个有序数列。需要提供以下操作：翻转一个区间，如原有序列为{ 5 4 3 2 1 }，翻转区间为[ 2 ，4 ]，数据结果为{ 5 2 3 4 1 }。数列中有n个数，翻转m次，1≤ n，m ≤ 100000。

输入样例	输出样例
5 3 1 3 1 3 1 4	4 3 2 1 5

文艺平衡树

#include<bits/stdc++.h>
using namespace std;
const int M = 1e5+10;
int cnt = 0, root = 0;
struct Node{int ls,rs,num,pri,size,lazy;}t[M];           //lazy懒标记，参考线段树
void newNode(int x){
  cnt++;
  t[cnt].size = 1; t[cnt].ls = t[cnt].rs = 0; t[cnt].pri = rand(); 
  t[cnt].num = x;                                        //本题不是按num分裂，是按排名分裂
}
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;}
void pushdown(int u){                                    //下传lazy标记。如果用splay实现，也是这样做
  if(t[u].lazy) {
    swap(t[u].ls, t[u].rs);                              //翻转u的左右部分，翻转不会破坏优先级pri
    t[t[u].ls].lazy ^= 1; t[t[u].rs].lazy ^= 1;          //向左右子树下传lazy
    t[u].lazy = 0;                                       //清除标记
  }
}
void Split(int u,int x,int &L,int &R){                   //排名分裂。返回：L，前x个数；R，其他数
  if(u == 0){L = R = 0; return ;}                        //到达叶子，递归返回
  pushdown(u);                                           //处理lazy标记
  if(t[t[u].ls].size+1 <= x){                            //第x个数在u的右子树上
    L = u; Split(t[u].rs, x-t[t[u].ls].size-1, t[u].rs, R);
  }
  else{ R = u; Split(t[u].ls,x,L,t[u].ls);}              //第x个数在左子树上
  Update(u);
}
int Merge(int L,int R){                                  //合并
  if(L==0 || R==0) return L+R;
  if(t[L].pri > t[R].pri){                               //左树L优先级大于右树R，则L节点是父结点
    pushdown(L);                                         //处理lazy标记
    t[L].rs = Merge(t[L].rs,R); Update(L); return L;
  }
  else{                                                  //合并后R是父结点
    pushdown(R);
    t[R].ls = Merge(L,t[R].ls); Update(R); return R;
  }
}
void inorder(int u){                                     //中序遍历，打印结果
  if(u == 0) return;
  pushdown(u);                                           //处理lazy
  inorder(t[u].ls); cout<<t[u].num<<" "; inorder(t[u].rs);            //中序遍历
}
int main(){
  srand(time(NULL));
  int n,m; cin >> n >>m;
  for(int i=1;i<=n;i++){newNode(i); root = Merge(root,cnt);}          //建树，本题比较简单
  while(m--){
    int x,y; cin >> x >> y;
    int L,R,p;                                          //三棵树，分别指向三棵树的根结点
    Split(root,y,L,R);                                  //分裂成L,p,R三棵树，p是[x,y]区间
    Split(L,x-1,L,p);
    t[p].lazy ^= 1;                                     //对p用lazy记录翻转
    root = Merge(Merge(L,p),R);                         //合并，还原成一棵树。
  }
  inorder (root);                                       //输出
  return 0;
}

笔记：文艺平衡树与普通平衡树的最大的不同：即下标从小到大，而不是里面的值从小到大！建树就是新建节点，再合并到树上，区间反转，分裂三棵树，p树用lazy标记，最后输出时处理