treap模板

期望复杂度为O(nlogn)

带合并的treap期望复杂度为O(nlognlogn)

1 #include 
      
         2 const int N = 1e6+10;  3 struct tree{  4     int l, r;//左右儿子节点编号  5     int num;//当前节点的数字  6     int s;//以当前节点为根的子树的节点数  7     int sum;//当前节点的数字的数量  8     int rnd;//随机优先级  9 }tr[N]; 10 int rt, cnt, t1, t2; 11 void updata(int &k){ 12     int &l = tr[k].l, &r = tr[k].r; 13     tr[k].s = tr[l].s+tr[r].s+tr[k].sum; 14 } 15 void lturn(int &k){ 16     int t = tr[k].r; 17     tr[k].r = tr[t].l; tr[t].l = k; tr[t].s = tr[k].s; 18     updata(k); k = t; 19 } 20 void rturn(int &k){ 21     int t = tr[k].l; 22     tr[k].l = tr[t].r; tr[t].r = k; tr[t].s = tr[k].s; 23     updata(k); k = t; 24 } 25 void insert(int &k, int x){ 26     if(!k){ 27         k = ++cnt; 28         tr[k].l = tr[k].r = 0; 29         tr[k].num = x; 30         tr[k].s = tr[k].sum = 1; 31         tr[k].rnd = rand(); 32         return ; 33     } 34     tr[k].s++; 35     int &l = tr[k].l, &r = tr[k].r; 36     if(x < tr[k].num){ 37         insert(l, x); 38         if(tr[l].rnd < tr[k].rnd) rturn(k); 39     } 40     else if(x > tr[k].num){ 41         insert(r, x); 42         if(tr[r].rnd < tr[k].rnd) lturn(k); 43     } 44     else tr[k].sum++; 45 } 46 void del(int &k, int x){ 47     if(!k) return ; 48     int &l = tr[k].l, &r = tr[k].r; 49     if(x == tr[k].num){ 50         if(tr[k].sum > 1){ 51             tr[k].sum--; tr[k].s--; 52             return ; 53         } 54         if(l*r == 0) k = l+r; 55         else{ 56             if(tr[l].rnd < tr[r].rnd) rturn(k); 57             else lturn(k); 58             del(k, x); 59         } 60     } 61     else{ 62         tr[k].s--; 63         if(x > tr[k].num) del(r,x); 64         else del(l,x); 65     } 66 } 67 int find1(int &k, int x){
    //查询 < x 的个数 68     if(!k) return 0; 69     int &l = tr[k].l, &r = tr[k].r; 70     if(tr[k].num == x) return tr[l].s; 71     if(tr[k].num > x) return find1(l, x); 72     if(tr[k].num < x) return tr[l].s+tr[k].sum+find1(r,x); 73 } 74 int find2(int &k, int x){
    //查询排名为x的数 75     if(!k) return 0; 76     int &l = tr[k].l, &r = tr[k].r; 77     if(tr[l].s+1 <= x&&tr[l].s+tr[k].sum >= x) return tr[k].num; 78     if(tr[l].s >= x) return find2(l, x); 79     if(tr[l].s+tr[k].sum < x) return find2(r, x-tr[l].s-tr[k].sum); 80 } 81 //以下不常用 82 void pred(int &k, int x){
    //t1 = 小于x的最大数 83     if(!k) return ; 84     int &l = tr[k].l, &r = tr[k].r; 85     if(tr[k].num < x){ 86         t1 = tr[k].num; 87         pred(r, x); 88     } 89     else pred(l, x); 90 } 91 void succ(int &k, int x){
    //t2 = 大于x的最小数 92     if(!k) return ; 93     int &l = tr[k].l, &r = tr[k].r; 94     if(tr[k].num > x){ 95         t2 = tr[k].num; 96         succ(l, x); 97     } 98     else succ(r, x); 99 }100 void mergeto(int &src, int &dest){
    //合并堆, 请确保src为根的子树大小小于dest, 需要O(nlogn)空间101     if(tr[src].l) mergeto(tr[src].l, dest);102     if(tr[src].r) mergeto(tr[src].r, dest);103     insert(dest, tr[src].num);104     src = 0;105 }106 int main(){107     srand(time(0));108     int n;109     scanf("%d", &n);110     rt = cnt = 0;//init111     for(int i = 1, opt, x; i <= n; i++){112         scanf("%d%d", &opt, &x);113         t1 = t2 = 0;114         switch(opt){115             case 1:insert(rt, x); break;//插入一个x116             case 2:del(rt, x); break;//删除一个x117             case 3:printf("%d\n", find1(rt, x)); break;//统计小于x的个数118             case 4:printf("%d\n", find2(rt, x)); break;//求排第x的数119             case 5:pred(rt, x); printf("%d\n", t1); break;120             case 6:succ(rt, x); printf("%d\n", t2); break;121         }122     }123     return 0;124 }