飞旋treap

忘是亡心i 2021-12-22 16:47 221阅读 0赞

虽然叫做非旋treap但是飞旋treap很带感所以就用这个名字了(SB)

这个东西是**真的好写**......

主要的两个函数只有两个，rotate和splay，split和merge。

merge就是大家都熟悉的左偏树合并，线段树合并......注意不能swap(x, y)

split分为splitV和splitS，按权值分，按大小分。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 inline void splitS(int o, int k, int &x, int &y) {
     2     if(!o) {
     3         x = y = 0;
     4         return;
     5     }
     6     //pushdown(o);
     7     if(k <= siz[ls[o]]) {
     8         y = o;
     9         splitS(ls[y], k, x, ls[y]);
    10     }
    11     else {
    12         x = o;
    13         splitS(rs[x], k - siz[ls[o]] - 1, rs[x], y);
    14     }
    15     pushup(o);
    16     return;
    17 }

splitS

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 inline void splitV(int o, int k, int &x, int &y) {
     2     if(!o) {
     3         x = y = 0;
     4         return;
     5     }
     6     pushdown(o);
     7     if(val[o] <= k) {
     8         x = o;
     9         splitV(rs[x], k, rs[x], y);
    10     }
    11     else {
    12         y = o;
    13         splitV(ls[y], k, x, ls[y]);
    14     }
    15     pushup(o);
    16     return;
    17 }

splitV

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 inline int merge(int x, int y) {
     2     if(!x || !y) {
     3         return x | y;
     4     }
     5     if(rd[x] >= rd[y]) {
     6         pushdown(x);
     7         rs[x] = merge(rs[x], y);
     8         pushup(x);
     9         return x;
    10     }
    11     else {
    12         pushdown(y);
    13         ls[y] = merge(x, ls[y]);
    14         pushup(y);
    15         return y;
    16     }
    17 }

merge

这个东西写着一般不去重。

接下来放例题。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <algorithm>
      3 #include <climits>
      4 #include <cstdlib>
      5 #include <ctime>
      6 
      7 typedef long long LL;
      8 const int N = 100010, INF = 0x3f3f3f3f;
      9 
     10 int ls[N], rs[N], val[N], rd[N], siz[N], tot, root;
     11 
     12 inline void pushup(int o) {
     13     siz[o] = siz[ls[o]] + siz[rs[o]] + 1;
     14     return;
     15 }
     16 
     17 inline void pushdown(int o) {
     18     return;
     19 }
     20 
     21 inline void splitV(int o, int k, int &x, int &y) {
     22     if(!o) {
     23         x = y = 0;
     24         return;
     25     }
     26     pushdown(o);
     27     if(val[o] <= k) {
     28         x = o;
     29         splitV(rs[x], k, rs[x], y);
     30     }
     31     else {
     32         y = o;
     33         splitV(ls[y], k, x, ls[y]);
     34     }
     35     pushup(o);
     36     return;
     37 }
     38 
     39 inline int merge(int x, int y) {
     40     if(!x || !y) {
     41         return x | y;
     42     }
     43     if(rd[x] >= rd[y]) {
     44         pushdown(x);
     45         rs[x] = merge(rs[x], y);
     46         pushup(x);
     47         return x;
     48     }
     49     else {
     50         pushdown(y);
     51         ls[y] = merge(x, ls[y]);
     52         pushup(y);
     53         return y;
     54     }
     55 }
     56 
     57 inline int np(int k) {
     58     int o = ++tot;
     59     siz[o] = 1;
     60     rd[o] = (((LL)rand() << 16) + rand()) % LONG_MAX;
     61     val[o] = k;
     62     return o;
     63 }
     64 
     65 inline int getLP(int x) {
     66     while(ls[x]) {
     67         x = ls[x];
     68     }
     69     return x;
     70 }
     71 
     72 inline int getRP(int x) {
     73     while(rs[x]) {
     74         x = rs[x];
     75     }
     76     return x;
     77 }
     78 
     79 inline int cal(int l, int r, int k) {
     80     if(l == -INF && r == INF) {
     81         return k;
     82     }
     83     return std::min(k - l, r - k);
     84 }
     85 
     86 inline void out(int x) {
     87     if(ls[x]) {
     88         out(ls[x]);
     89     }
     90     printf("%d ", val[x]);
     91     if(rs[x]) {
     92         out(rs[x]);
     93     }
     94     return;
     95 }
     96 
     97 int main() {
     98     srand(time(0));
     99     int n;
    100     scanf("%d", &n);
    101     int x = np(-INF), y = np(INF);
    102     root = merge(x, y);
    103     LL ans = 0;
    104     for(int i = 1; i <= n; i++) {
    105         int k;
    106         scanf("%d", &k);
    107         splitV(root, k, x, y);
    108         //printf("X : "); out(x); puts("");
    109         //printf("Y : "); out(y); puts("");
    110         int a = getRP(x), b = getLP(y);
    111         ans += cal(val[a], val[b], k);
    112         root = merge(merge(x, np(k)), y);
    113         //out(root); puts("");
    114     }
    115     printf("%lld\n", ans);
    116     return 0;
    117 }

洛谷P2234 营业额统计

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <algorithm>
      3 #include <cstring>
      4 #include <cstdlib>
      5 #include <ctime>
      6 #include <climits>
      7 
      8 typedef long long LL;
      9 const int N = 100010, INF = 0x3f3f3f3f;
     10 
     11 int ls[N], rs[N], siz[N], val[N], rd[N], tot, root;
     12 
     13 inline void pushup(int x) {
     14     siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
     15     return;
     16 }
     17 
     18 inline int merge(int x, int y) {
     19     if(!x || !y) {
     20         return x | y;
     21     }
     22     if(rd[x] >= rd[y]) {
     23         //pushdown(x);
     24         rs[x] = merge(rs[x], y);
     25         pushup(x);
     26         return x;
     27     }
     28     else {
     29         //pushdown(y);
     30         ls[y] = merge(x, ls[y]);
     31         pushup(y);
     32         return y;
     33     }
     34 }
     35 
     36 inline void splitV(int o, int k, int &x, int &y) {
     37     if(!o) {
     38         x = y = 0;
     39         return;
     40     }
     41     //pushdown(o);
     42     //printf("o = %d \n", o);
     43     if(val[o] <= k) {
     44         x = o;
     45         splitV(rs[x], k, rs[x], y);
     46     }
     47     else {
     48         y = o;
     49         splitV(ls[y], k, x, ls[y]);
     50     }
     51     pushup(o);
     52     return;
     53 }
     54 
     55 inline void splitS(int o, int k, int &x, int &y) {
     56     if(!o) {
     57         x = y = 0;
     58         return;
     59     }
     60     //pushdown(o);
     61     if(k <= siz[ls[o]]) {
     62         y = o;
     63         splitS(ls[y], k, x, ls[y]);
     64     }
     65     else {
     66         x = o;
     67         splitS(rs[x], k - siz[ls[o]] - 1, rs[x], y);
     68     }
     69     pushup(o);
     70     return;
     71 }
     72 
     73 inline int np(int k) {
     74     int o = ++tot;
     75     siz[o] = 1;
     76     val[o] = k;
     77     rd[o] = (((LL)rand() << 16) + rand()) % LONG_MAX;
     78     return o;
     79 }
     80 
     81 inline void insert(int k) {
     82     int x, y;
     83     splitV(root, k, x, y);
     84     root = merge(merge(x, np(k)), y);
     85     return;
     86 }
     87 
     88 inline int getLP(int x) {
     89     while(ls[x]) {
     90         x = ls[x];
     91     }
     92     return x;
     93 }
     94 
     95 inline int getRP(int x) {
     96     while(rs[x]) {
     97         x = rs[x];
     98     }
     99     return x;
    100 }
    101 
    102 inline int getVbyR(int k) {
    103     int x, y;
    104     splitS(root, k, x, y);
    105     int t = val[getLP(y)];
    106     root = merge(x, y);
    107     return t;
    108 }
    109 
    110 inline int getRbyV(int k) {
    111     int x, y;
    112     splitV(root, k - 1, x, y);
    113     int t = siz[x];
    114     root = merge(x, y);
    115     return t;
    116 }
    117 
    118 inline int getPre(int k) {
    119     int x, y;
    120     splitV(root, k - 1, x, y);
    121     int t = val[getRP(x)];
    122     root = merge(x, y);
    123     return t;
    124 }
    125 
    126 inline int getNex(int k) {
    127     int x, y;
    128     splitV(root, k, x, y);
    129     int t = val[getLP(y)];
    130     root = merge(x, y);
    131     return t;
    132 }
    133 
    134 inline void del(int k) {
    135     int x, y, z;
    136     splitV(root, k - 1, x, y);
    137     splitS(y, 1, z, y);
    138     root = merge(x, y);
    139     return;
    140 }
    141 
    142 int main() {
    143     srand(time(0));
    144     int n;
    145     scanf("%d", &n);
    146     root = merge(np(-INF), np(INF));
    147 
    148     for(int i = 1, f, x; i <= n; i++) {
    149         scanf("%d%d", &f, &x);
    150         if(f == 1) insert(x);
    151         else if(f == 2) del(x);
    152         else if(f == 3) printf("%d\n", getRbyV(x));
    153         else if(f == 4) printf("%d\n", getVbyR(x));
    154         else if(f == 5) printf("%d\n", getPre(x));
    155         else if(f == 6) printf("%d\n", getNex(x));
    156     }
    157 
    158     return 0;
    159 }

洛谷P3369 普通平衡树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
      2 #include <algorithm>
      3 #include <cstdlib>
      4 #include <ctime>
      5 #include <cstring>
      6 #include <climits>
      7 
      8 typedef long long LL;
      9 const int N = 100010;
     10 
     11 int ls[N], rs[N], val[N], rd[N], siz[N], tot, root;
     12 bool rev[N];
     13 
     14 inline void pushup(int x) {
     15     siz[x] = siz[ls[x]] + siz[rs[x]] + 1;
     16     return;
     17 }
     18 
     19 inline void pushdown(int x) {
     20     if(rev[x]) {
     21         std::swap(ls[x], rs[x]);
     22         if(ls[x]) {
     23             rev[ls[x]] ^= 1;
     24         }
     25         if(rs[x]) {
     26             rev[rs[x]] ^= 1;
     27         }
     28         rev[x] = 0;
     29     }
     30     return;
     31 }
     32 
     33 inline int merge(int x, int y) {
     34     if(!x || !y) {
     35         return x | y;
     36     }
     37     if(rd[x] >= rd[y]) {
     38         pushdown(x);
     39         rs[x] = merge(rs[x], y);
     40         pushup(x);
     41         return x;
     42     }
     43     else {
     44         pushdown(y);
     45         ls[y] = merge(x, ls[y]);
     46         pushup(y);
     47         return y;
     48     }
     49 }
     50 
     51 inline void splitS(int o, int k, int &x, int &y) {
     52     if(!o) {
     53         x = y = 0;
     54         return;
     55     }
     56     pushdown(o);
     57     if(k <= siz[ls[o]]) {
     58         y = o;
     59         splitS(ls[y], k, x, ls[y]);
     60     }
     61     else {
     62         x = o;
     63         splitS(rs[x], k - siz[ls[o]] - 1, rs[x], y);
     64     }
     65     pushup(o);
     66     return;
     67 }
     68 
     69 inline int np(int k) {
     70     int o = ++tot;
     71     siz[o] = 1;
     72     val[o] = k;
     73     rd[o] = (((LL)rand() << 16) + rand()) % LONG_MAX;
     74     return o;
     75 }
     76 
     77 inline void reverse(int l, int r) {
     78     int x, y, z;
     79     splitS(root, l, x, y);
     80     splitS(y, r - l + 1, y, z);
     81     rev[y] ^= 1;
     82     root = merge(merge(x, y), z);
     83     return;
     84 }
     85 
     86 inline void insert(int p, int k) {
     87     int x, y;
     88     splitS(root, p + 1, x, y);
     89     root = merge(merge(x, np(k)), y);
     90     return;
     91 }
     92 
     93 void out(int x) {
     94     pushdown(x);
     95     if(ls[x]) out(ls[x]);
     96     if(val[x]) printf("%d ", val[x]);
     97     if(rs[x]) out(rs[x]);
     98     return;
     99 }
    100 
    101 int main() {
    102     int n, m;
    103     scanf("%d%d", &n, &m);
    104     root = merge(np(0), np(0));
    105     for(int i = 1; i <= n; i++) {
    106         insert(i - 1, i);
    107     }
    108     for(int i = 1, x, y; i <= m; i++) {
    109         scanf("%d%d", &x, &y);
    110         reverse(x, y);
    111     }
    112     out(root);
    113     return 0;
    114 }

洛谷P3391 文艺平衡树

注意不要把split里的o写成x.....

转载于:https://www.cnblogs.com/huyufeifei/p/10406846.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/3d9e64b24f54477c806c71ad23732efc.png