想不到我一把年纪了还要被回炉重造,感谢CP
我记得好像写过一个平衡树的了?
这次写是因为碰到作业题,是一个大号的贪心背包问题,思路不难整,但是需要特殊数据结构的加持
其实就是一个更新所有大于 x的数字要求减去一个特定的值,再在相应的位置上打标,然后搜了半天搜到了fhq treap
首先我之前写平衡树跳过了treap,所以学fhq treap不得不从treap开始看
其实也没啥难理解的,就是只要理解了这个左旋和右旋,其他其实就和平衡二叉树无异了
然后模板是借鉴一个csdn博主的,贴到这里只是为了我自己用而已
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <bits/stdc++.h> using namespace std; constexpr int limit = (3000000 + 5);//防止溢出 #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f #define lowbit(i) i&(-i)//一步两步 #define EPS 1e-9 #define FASTIO ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); #define ff(a) printf("%d\n",a ); #define pi(a, b) pair<a,b> #define rep(i, a, b) for(ll i = a; i <= b ; ++i) #define per(i, a, b) for(ll i = b ; i >= a ; --i) #define MOD 998244353 #define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next) #define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin) #define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout) typedef long long ll; typedef unsigned long long ull; char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; inline ll read() { #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) ll sign = 1, x = 0; char s = getchar(); while (s > '9' || s < '0') { if (s == '-')sign = -1; s = getchar(); } while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + s - '0'; s = getchar(); } return x * sign; #undef getchar }//快读 void print(ll x) { if (x / 10) print(x / 10); *O++ = x % 10 + '0'; } void write(ll x, char c = 't') { if (x < 0)putchar('-'), x = -x; print(x); if (!isalpha(c))*O++ = c; fwrite(obuf, O - obuf, 1, stdout); O = obuf; } const ll mod = MOD; ll quickPow(ll base, ll expo){ ll ans = 1; while (expo){ if(expo & 1)(ans *= base) %= mod; expo >>= 1; base = base * base; base %= mod; } return ans % mod; } ll C(ll n, ll m){ if(n < m)return 0; ll x = 1, y = 1; if(m > n - m)m = n - m; rep(i ,0 , m - 1){ x = x * (n - i) % mod; y = y * (i + 1) % mod; } return x * quickPow(y, mod - 2) % mod; } int n, m, k; struct node{ int l, r; int key; int val; int cnt; int size; }tree[limit]; void update(int rt){ tree[rt].size = tree[tree[rt].l].size + tree[tree[rt].r].size + tree[rt].cnt; } int root, idx; int new_node(int key){ tree[++idx].key = key; tree[idx].val = rand(); tree[idx].cnt = tree[idx].size = 1; return idx; } void build(){ new_node(-INF),new_node(INF); root = 1,tree[1].r = 2; update(root); } //右旋 void right_rotate(int &rt){ int q = tree[rt].l; tree[rt].l = tree[q].r, tree[q].r = rt, rt = q;//rt再变回根 update(tree[rt].r); update(rt); } //左旋 void left_rotate(int &rt){ int q = tree[rt].r; tree[rt].r = tree[q].l; tree[q].l = rt; rt = q; update(tree[rt].l); update(rt); } void insert(int &rt,int key) { if(!rt) rt = new_node(key); else if (tree[rt].key == key)tree[rt].cnt ++; else if (tree[rt].key > key){ insert(tree[rt].l,key); if(tree[tree[rt].l].val > tree[rt].val) right_rotate(rt); } else{ insert(tree[rt].r,key); //右大左旋 if(tree[tree[rt].r].val > tree[rt].val) left_rotate(rt); } update(rt); } void del(int &rt,int key){ if(!rt) return ; if(tree[rt].key == key){ if(tree[rt].cnt > 1)tree[rt].cnt --; else if (tree[rt].l || tree[rt].r){ if(!tree[rt].r||tree[tree[rt].l].val > tree[tree[rt].r].val){ right_rotate(rt); del(tree[rt].r,key); } else{ left_rotate(rt); del(tree[rt].l,key); } } else rt = 0; }else if (tree[rt].key > key)del(tree[rt].l,key); else del(tree[rt].r,key); update(rt); } int get_rank(int rt, int key){ if (!rt) return 0; if (tree[rt].key == key) return tree[tree[rt].l].size + 1; if (tree[rt].key > key)return get_rank(tree[rt].l,key); return tree[tree[rt].l].size + tree[rt].cnt + get_rank(tree[rt].r,key); } int order_of(int rt, int rank){ if(!rt) return INF; if(tree[tree[rt].l].size >= rank) return order_of(tree[rt].l,rank); if(tree[tree[rt].l].size + tree[rt].cnt >= rank)return tree[rt].key; return order_of(tree[rt].r,rank - tree[tree[rt].l].size - tree[rt].cnt); } int prev(int rt, int key){ if(!rt) return -INF; if(tree[rt].key >= key) return ::prev(tree[rt].l,key); return max(tree[rt].key,::prev(tree[rt].r,key)); } int next(int rt, int key){ if(!rt) return INF; if(tree[rt].key <= key)return ::next(tree[rt].r,key); return min(tree[rt].key,::next(tree[rt].l,key)); } void solve(){ build(); cin>>n; rep(_, 1, n){ int op, val; cin>>op>>val; if(op == 1){ insert(root, val); }else if(op == 2){ del(root, val); }else if(op == 3){ cout<<(get_rank(root, val) - 1)<<endl; }else if(op == 4){ cout<<(order_of(root, val + 1))<<endl; }else if(op == 5){ cout<<::prev(root, val)<<endl; }else{ cout<<::next(root, val)<<endl; } } }; int32_t main() { #ifdef LOCAL FOPEN; // FOUT; #endif FASTIO // int kase; // cin>>kase; // while (kase--) solve(); cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n"; return 0; }View Code
标签:rt,return,val,int,tree,treap,key,模板 From: https://www.cnblogs.com/tiany7/p/16721512.html