旋转treap

查了半天才知道，原来旋转的treap不能实现区间操作！！

不过还是要学的。。。

zip//右旋

void zip(int &k)//右旋 
{
    int y=lc(k);
    lc(k)=rc(y);
    rc(y)=k;
    s(y)=s(k);
    upt(k);
    k=y;
}

View Code

zap//左旋

void zap(int &k)//左旋 
{
    int y=rc(k);
    rc(k)=lc(y);
    lc(y)=k;
    s(y)=s(k);
    upt(k);
    k=y;
}

View Code

insert//插入

　　1.终止，添加单点信息

　　2.修改size

　　3.向下插入（先插后旋）

void Insert(int &k,int &key)//插入 
{
    if(!k)
    {
        k=++nt,v(k)=key,p(k)=rand();//从1开始 
        s(k)=c(k)=1,lc(k)=rc(k)=0;
        return;
    }
    s(k)++;
    if(v(k)==key) c(k)++;
    else 
        if(v(k)>key) 
        {
            Insert(lc(k),key);
            if(p(lc(k))<p(k)) zip(k); 
        } 
        else{
            Insert(rc(k),key);
            if(p(rc(k))<p(k)) zap(k); 
        }
    return;
}

View Code

Delete//删除 
　　1.查找到，删除（先旋后删）
　　2.修改size
　　3.向下查找

void Delete(int &k,int &key)//删除
{
    if(v(k)==key)
    {
        if(c(k)>1) c(k)--,s(k)--;
        else if(!lc(k) or !rc(k)) k=lc(k)+rc(k);
             else if(p(lc(k))<p(rc(k))) zip(k),Delete(k,key);
                     else zap(k),Delete(k,key);
        return;
    }
    s(k)--;
    if(key<v(k)) Delete(lc(k),key);
    else Delete(rc(k),key);
    return;
}

View Code

queryrank//查询此元素的名次（如有重复元素,返回最高名次）

int queryrank(int &key)//查询此元素的名次（如有重复元素,返回最高名次） 
{
    int k=rt,re=0;
    while(k)
    {
        if(key==v(k)) return re+s(lc(k))+1;
        else if(key<v(k)) k=lc(k);
             else re+=s(lc(k))+c(k),k=rc(k);
    }
    return re;
}

View Code

querykth//查询第k小的元素

int querykth(int k)//查询第k小的元素
{
    int x=rt;
    while(x)
    {
        if(k>s(lc(x)) and k<=s(lc(x))+c(x)) return v(x);
        else if(k<=s(lc(x))) x=lc(x);
             else k-=s(lc(x))+c(x),x=rc(x); 
    }
    return v(x);
}

View Code

querypre//查询元素的前驱

int querypre(int &key)//查询元素的前驱 
{
    int x=rt,re=2e9; 
    while(x)
    {
        if(v(x)<key) re=v(x),x=rc(x);
        else x=lc(x);
    }
    return re;
}

View Code

querysur//查询元素的后驱

 1 int querysur(int &key)//查询元素的后驱 
 2 {
 3     int x=rt,re=2e9; 
 4     while(x)
 5     {
 6         if(v(x)>key) re=v(x),x=lc(x);
 7         else x=rc(x);
 8     }
 9     return re;
10 }

View Code

来个总代码（洛谷3369（https://www.luogu.org/problemnew/show/P3369））

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 void upt(int &k);
  6 void zip(int &k);//右旋 
  7 void zap(int &k);//左旋 
  8 void Insert(int &k,int &key);//插入
  9 void Delete(int &k,int &key);//删除 
 10 int queryrank(int &key);//查询此元素的名次（如有重复元素,返回最高名次）
 11 int querykth(int k);//查询第k小的元素
 12 int querypre(int &key);//查询元素的前驱 
 13 int querysur(int &key);//查询元素的后驱 
 14 void read(int &x);
 15 void write(int x);
 16 struct node{
 17     int lc,rc,key,priority,size,cnt;
 18     #define lc(k) a[k].lc
 19     #define rc(k) a[k].rc
 20     #define v(k) a[k].key
 21     #define p(k) a[k].priority
 22     #define s(k) a[k].size
 23     #define c(k) a[k].cnt
 24 };
 25 node a[100050];
 26 int nt=0,rt;//附属条件 
 27 int main()
 28 {
 29     int n;
 30     read(n);
 31     int q,s;
 32     for(int i=1;i<=n;i++)
 33     {
 34         read(q),read(s);
 35         if(q==1) Insert(rt,s);
 36         if(q==2) Delete(rt,s);
 37         if(q==3) write(queryrank(s)),putchar('\n');
 38         if(q==4) write(querykth(s)),putchar('\n');
 39         if(q==5) write(querypre(s)),putchar('\n');
 40         if(q==6) write(querysur(s)),putchar('\n');
 41     }
 42     return 0;
 43 } 
 44 void upt(int &k) {s(k)=s(lc(k))+s(rc(k))+c(k);}
 45 void zip(int &k)//右旋 
 46 {
 47     int y=lc(k);
 48     lc(k)=rc(y);
 49     rc(y)=k;
 50     s(y)=s(k);
 51     upt(k);
 52     k=y;
 53 }
 54 void zap(int &k)//左旋 
 55 {
 56     int y=rc(k);
 57     rc(k)=lc(y);
 58     lc(y)=k;
 59     s(y)=s(k);
 60     upt(k);
 61     k=y;
 62 }
 63 void Insert(int &k,int &key)//插入 
 64 {
 65     if(!k)
 66     {
 67         k=++nt,v(k)=key,p(k)=rand();//从1开始 
 68         s(k)=c(k)=1,lc(k)=rc(k)=0;
 69         return;
 70     }
 71     s(k)++;
 72     if(v(k)==key) c(k)++;
 73     else 
 74         if(v(k)>key) 
 75         {
 76             Insert(lc(k),key);
 77             if(p(lc(k))<p(k)) zip(k); 
 78         } 
 79         else{
 80             Insert(rc(k),key);
 81             if(p(rc(k))<p(k)) zap(k); 
 82         }
 83     return;
 84 } 
 85 void Delete(int &k,int &key)//删除
 86 {
 87     if(v(k)==key)
 88     {
 89         if(c(k)>1) c(k)--,s(k)--;
 90         else if(!lc(k) or !rc(k)) k=lc(k)+rc(k);
 91              else if(p(lc(k))<p(rc(k))) zip(k),Delete(k,key);
 92                      else zap(k),Delete(k,key);
 93         return;
 94     }
 95     s(k)--;
 96     if(key<v(k)) Delete(lc(k),key);
 97     else Delete(rc(k),key);
 98     return;
 99 }
100 int queryrank(int &key)//查询此元素的名次（如有重复元素,返回最高名次） 
101 {
102     int k=rt,re=0;
103     while(k)
104     {
105         if(key==v(k)) return re+s(lc(k))+1;
106         else if(key<v(k)) k=lc(k);
107              else re+=s(lc(k))+c(k),k=rc(k);
108     }
109     return re;
110 }
111 int querykth(int k)//查询第k小的元素
112 {
113     int x=rt;
114     while(x)
115     {
116         if(k>s(lc(x)) and k<=s(lc(x))+c(x)) return v(x);
117         else if(k<=s(lc(x))) x=lc(x);
118              else k-=s(lc(x))+c(x),x=rc(x); 
119     }
120     return v(x);
121 } 
122 int querypre(int &key)//查询元素的前驱 
123 {
124     int x=rt,re=2e9; 
125     while(x)
126     {
127         if(v(x)<key) re=v(x),x=rc(x);
128         else x=lc(x);
129     }
130     return re;
131 }
132 int querysur(int &key)//查询元素的后驱 
133 {
134     int x=rt,re=2e9; 
135     while(x)
136     {
137         if(v(x)>key) re=v(x),x=lc(x);
138         else x=rc(x);
139     }
140     return re;
141 }
142 void read(int &x)
143 {
144     x=0;
145     int i=1;
146     char c=getchar();
147     while(c<'0' or c>'9')
148     {
149         if(c=='-') i=-1;
150         c=getchar();
151     }
152     while(c>='0' and c<='9')
153     {
154         x=x*10+c-'0';
155         c=getchar();
156     }
157     x*=i;
158 }
159 void write(int x)
160 {
161     if(x<0) putchar('-'),x*=-1;
162     if(x>9) write(x/10);
163     putchar(x%10+'0');
164 }

View Code