平衡树写题记录

练思维的同时还是顺便点一下科技树吧。。。顺便fhq-treap好写好用，再也不用Splay了，反正不学LCT了。

这下面是实现大多数功能的fhq-treap板子

 1 mt19937 rnd(time(0));
 2 struct fhq_treap {
 3     int size[maxn],ls[maxn],rs[maxn],val[maxn],tot,wei[maxn],root;
 4     fhq_treap() {tot = 0;}
 5     int New(int v) {
 6         size[++tot] = 1;
 7         val[tot] = v;
 8         wei[tot] = rnd();
 9         return tot;
10     }
11     void pushup(int p) {size[p] = size[ls[p]] + size[rs[p]] + 1;}
12     void Split(int p, int v, int &x, int &y) {
13         if(!p) {x = 0; y = 0; return;}
14         if(val[p] <= v){x = p; Split(rs[p], v, rs[p], y);}
15         else {y = p; Split(ls[p], v, x, ls[p]);}
16         pushup(p);
17     }
18     int Merge(int x, int y) {
19         if((!x) || (!y)) return x + y;
20         if(wei[x] < wei[y]) {
21             ls[y] = Merge(x, ls[y]);
22             pushup(y);
23             return y;
24         }
25         else {
26             rs[x] = Merge(rs[x], y);
27             pushup(x);
28             return x;
29         }
30     }
31     void insert(int v) {
32         int x,y;
33         Split(root, v - 1, x, y);
34         root = Merge(Merge(x, New(v)), y);
35     }
36     void del(int v) {
37         int x,y,z;
38         Split(root, v, x, z);
39         Split(x, v - 1, x, y);
40         root = Merge(Merge(x, Merge(ls[y], rs[y])), z);
41     }
42     int find(int p, int kth) {
43         if(size[ls[p]] + 1 == kth) return p;
44         if(kth < size[ls[p]] + 1) return find(ls[p], kth);// 又写反了。。 
45         return find(rs[p], kth - size[ls[p]] - 1);
46     }
47     int rnk(int v) {
48         int x,y,ret;
49         Split(root, v - 1, x, y);
50         ret = size[x] + 1;
51         root = Merge(x, y);
52         return ret;
53     }
54     int pre(int v) {
55         int x,y,ret;
56         Split(root, v - 1, x, y);
57         ret = val[find(x, size[x])];
58         root = Merge(x, y);
59         return ret;
60     }
61     int nxt(int v) {
62         int x,y,ret;
63         Split(root, v, x, y);
64         ret = val[find(y, 1)];
65         root = Merge(x, y);
66         return ret;
67     }
68 }t;

有下传标记操作就在split和merge递归开头pushdown就好了，区间树有时间再补

HNOI2002 营业额统计

链接 挺傻的一个题，set都能水过去，写个查前驱后继的平衡树就可以了，记得判重复

TJOI2007 书架

链接 还是比较简单的，考虑像map那样每个节点开两个值：字符串、排名。然后按排名为关键字排序就可以了。插入的时候按v-1分裂，像线段树那样给大一点的那棵树打上区间加标记，分裂合并时下传标记就可以了，查询跟rnk查值一样的，写个find就可以了。