文艺平衡树（无旋treap）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace std;
  7 struct NODE{
  8     NODE *ls,*rs;
  9     int r,s,v;
 10     int rev;
 11     #define size(x) ((x)?(x)->s:0)
 12     NODE(int v=0):v(v){
 13         r=rand();
 14         ls=rs=NULL;
 15         s=1;
 16         rev=0;
 17     }
 18     void reverse(){
 19         if(!this) return;
 20         swap(ls,rs);
 21         rev^=1;
 22     }
 23     void pushdown(){
 24         if(!this) return;
 25         if(rev){
 26             ls->reverse();
 27             rs->reverse();
 28             rev^=1;
 29         }
 30     }
 31     void mt(){
 32         s=1+size(ls)+size(rs);
 33     }
 34 };
 35 
 36 typedef NODE *pnode;
 37 typedef pair<NODE*,NODE*>droot;
 38 NODE *merge(NODE *a,NODE *b){//treap为了满足中序序列，左右子树不能交换 
 39     if(!a) return b;
 40     if(!b) return a;
 41     if(a->r < b->r){//小根堆 
 42         a->pushdown();
 43         a->rs=merge(a->rs,b);
 44         a->mt();
 45         return a; 
 46     }
 47     else {
 48         b->pushdown();
 49         b->ls=merge(a,b->ls);
 50         b->mt();
 51         return b;
 52     }
 53 }
 54 droot split(NODE *x,int k){
 55     if(!x) return droot(NULL,NULL);
 56     x->pushdown();
 57     droot r;
 58     if(size(x->ls) >= k){
 59         r=split(x->ls,k);
 60         x->ls=r.second;
 61         x->mt();
 62         r.second=x;
 63     }
 64     else {
 65         r=split(x->rs,k-size(x->ls)-1);
 66         x->rs=r.first;
 67         x->mt();
 68         r.first=x;
 69     }
 70     return r;
 71 }
 72 //名次树用的普通写法
 73 int kth(NODE *x,int k){//
 74     if(!x || k<=0 || k>size(x)) return 0;
 75     int s=size(x->rs);
 76     if(k == s+1) return x->v;
 77     else if(k <= s) return kth(x->ls,k);
 78     else return kth(x->rs,k-size(x->ls)-1);
 79 } 
 80 int rank(NODE *x,int v){
 81     if(!x) return 0;
 82     if(v < x->v) return rank(x->ls,v);
 83     else return rank(x->rs,v)+size(x->ls)+1;
 84 }
 85 NODE *insert(NODE *root,int v){
 86     int k=rank(root,v);
 87     droot x=split(root,k);
 88     NODE *o=new NODE(v);
 89     return merge(merge(x.first,o),x.second);
 90 }
 91 NODE *build(int *a,int n){
 92     pnode *stk=new pnode[n];
 93     NODE *last;
 94     int tp=0;
 95     for(int i=1;i<=n;i++){
 96         NODE *p=new NODE(i);
 97         last=NULL;
 98         while(tp && stk[tp-1]->r > p->r){
 99             stk[tp-1]->mt();
100             last=stk[tp-1];
101             stk[--tp]=NULL;
102         }
103         if(tp) stk[tp-1]->rs=p;
104         p->ls=last;
105         stk[tp++]=p;
106     }
107     while(tp) stk[--tp]->mt();
108     NODE *r=stk[0];
109     delete []stk;
110     return r;
111 }
112 
113 void dfs(NODE *u){
114     if(!u) return;
115     u->pushdown();
116     dfs(u->ls);
117     printf("%d ",u->v);
118     dfs(u->rs);
119 }
120 
121 int n,m;
122 int d[100010];
123 int main(){
124     freopen("sph.in", "r", stdin);
125     freopen("sph.out", "w", stdout);
126     scanf("%d %d",&n,&m);
127     NODE *t=build(d,n);
128     while(m--){
129         int l,r;
130         scanf("%d %d",&l,&r);
131         droot p1=split(t,l-1);
132         droot p2=split(p1.second,r-l+1);
133         p2.first->reverse();
134         t=merge(p1.first,merge(p2.first,p2.second));
135     }
136     dfs(t);
137     return(0);
138 }