初探treap

treap的基本操作

poj1338 Ugly Numbers

把质因子只含2,3,5的数叫Ugly Number.通式为:

$$x=2^i \times 3^j \times 5^k$$

注意到是一个幂次计算，因此大致地有:

$$0\le i,j,k \le 30$$ 那么我们只需要枚举 $\prod_{(0\le i \le30,\;x=2,3,5)}\quad x_i$，然后排序即可。当然也可以直接 $logn$地插入，于是可以用 $\mathtt STL$的 $set$维护，这里不用set，用Treap维护一下，每个节点还要增加一个 $rank$，用来维护子树节点的数量。
代码：

#include 
      #include 
      #include 
      #include 
      #include 
      using namespace std; typedef long long type; struct node { type val; int fix; int rank; //增加维护一个rank值,保存以该节点为根子树的节点数目 node* left; node* right; node() { left = right = NULL; } node(type x) { val = x; fix = rand(); left = right = NULL; } }; inline int rank(node* &T) { return T == NULL ? 0 : T->rank; } void rotate_left(node* &T) { //printf("rotate_left %d\n", T->val); node* tp = T->right; T->right = tp->left; T->rank = rank(T->left) + rank(T->right) + 1; tp->left = T; tp->rank = rank(tp->left) + rank(tp->right) + 1; T = tp; } void rotate_right(node* &T) { //printf("rotate_right %d\n", T->val); node* tp = T->left; T->left = tp->right; T->rank = rank(T->left) + rank(T->right) + 1; tp->right = T; tp->rank = rank(tp->left) + rank(tp->right) + 1; T = tp; } void insert(node* &T, type& val) { if (T == NULL) { T = new node(val); T->rank = 1; } else if (val == T->val) { return; } else if (val < T->val) { insert(T->left, val); ++T->rank; if (T->left->fix < T->fix) { rotate_right(T); } } else { insert(T->right, val); ++T->rank; if (T->right->fix < T->fix) { rotate_left(T); } } } void erase(node* &T, type& val) { if (val == T->val) { if (T->left == NULL || T->right == NULL) { node* t = T; if (T->left == NULL) { T = T->right; } else { T = T->left; } T->rank = rank(T->left) + rank(T->right) + 1; delete t; } else { if (T->left->fix < T->right->fix) { rotate_right(T); erase(T->right, val); } else { rotate_left(T); erase(T->left, val); } } } else if (val < T->val) { erase(T->left, val); --(T->rank); } else { erase(T->right, val); --(T->rank); } } bool exist(node* &T, type val) { if (T == NULL) { return false; } else if (T->val == val) { return true; } else if (val < T->val) { return exist(T->left, val); } else { return exist(T->right, val); } } void clear(node* &T) { if (T == NULL) return; clear(T->left); clear(T->right); delete T; T = NULL; } const type INF = 0xfffffff; type find_k(node* &T, int k) { //printf("find_k(%d)\n", k); if (k <= 0 || k > rank(T)) { return INF; } else if (k == rank(T->left) + 1) { return T->val; } else if (k <= rank(T->left)) { return find_k(T->left, k); } else { return find_k(T->right, k - 1 - rank(T->left)); } } void visit(node* &T) { if (T == NULL) return; visit(T->left); printf("(%d,%d) ", T->val, T->rank); visit(T->right); } const int MAX = 32; type p2[MAX], p3[MAX], p5[MAX]; int main() { p2[0] = p3[0] = p5[0] = 1; for (int i = 1; i < MAX; ++i) { p2[i] = p2[i - 1] << 1; p3[i] = p3[i - 1] * 3; p5[i] = p5[i - 1] * 5; } node* T = NULL; for (int i = 0; i < MAX; ++i) { if (p2[i] <= 0) break; for (int j = 0; j < MAX; ++j) { if (p3[j] <= 0) break; for (int k = 0; k < MAX; ++k) { long long t = p2[i] * p3[j] * p5[k]; if (t <= 0) break; //printf("insert %d\n", t); insert(T, t); } } } //visit(T); //puts(""); int n; while (~scanf(" %d", &n)) { if (n == 0) break; printf("%lld\n", find_k(T, n)); } clear(T); return 0; }

poj1552

这题只需要用到查找操作，遍历维护的$treap$，对任意节点$x$只需要检查是否存在元素$2\times x$即可。代码：

#include 
      #include 
      #include 
      #include 
      #include 
      using namespace std; typedef int type; struct node { type val; int fix; node* left; node* right; node() { left = right = NULL; } node(type x) { val = x; fix = rand(); left = right = NULL; } }; void rotate_left(node* &T) { node* tp = T->right; T->right = tp->left; tp->left = T; T = tp; } void rotate_right(node* &T) { node* tp = T->left; T->left = tp->right; tp->right = T; T = tp; } void insert(node* &T, type& val) { if (T == NULL) { T = new node(val); } else if (val <= T->val) { insert(T->left, val); if (T->left->fix < T->fix) { rotate_right(T); } } else { insert(T->right, val); if (T->right->fix < T->fix) { rotate_left(T); } } } void erase(node* &T, type& val) { if (val == T->val) { if (T->left == NULL || T->right == NULL) { node* t = T; if (T->left == NULL) { T = T->right; } else { T = T->left; } delete t; } else { if (T->left->fix < T->right->fix) { rotate_right(T); erase(T->right, val); } else { rotate_left(T); erase(T->left, val); } } } else if (val < T->val) { erase(T->left, val); } else { erase(T->right, val); } } bool exist(node* &T, type val) { if (T == NULL) { return false; } else if (T->val == val) { return true; } else if (val < T->val) { return exist(T->left, val); } else { return exist(T->right, val); } } void clear(node* &T) { if (T == NULL) return; clear(T->left); clear(T->right); delete T; T = NULL; } int query(node* &root, node* &T) { if (T == NULL) return 0; return exist(root, (T->val) * 2) + query(root, T->left) + query(root, T->right); } void visit(node* &T) { if (T == NULL) return; visit(T->left); printf("%d ", T->val); visit(T->right); } int main() { node* T = NULL; int n; while (~scanf(" %d", &n) && n != - 1) { while (n != 0) { insert(T, n); //visit(T); //puts(""); scanf(" %d", &n); } printf("%d\n", query(T, T)); clear(T); } return 0; }

HDU5058 So easy

#include 
      #include 
      #include 
      #include 
      #include 
      using namespace std; typedef int type; struct node { type val; int fix; node* left; node* right; node() { left = right = NULL; } node(type x) { val = x; fix = rand(); left = right = NULL; } }; void rotate_left(node* &T) { node* tp = T->right; T->right = tp->left; tp->left = T; T = tp; } void rotate_right(node* &T) { node* tp = T->left; T->left = tp->right; tp->right = T; T = tp; } void insert(node* &T, type& val) { if (T == NULL) { T = new node(val); } else if (val == T->val) { return; } else if (val < T->val) { insert(T->left, val); if (T->left->fix < T->fix) { rotate_right(T); } } else { insert(T->right, val); if (T->right->fix < T->fix) { rotate_left(T); } } } void erase(node* &T, type& val) { if (val == T->val) { if (T->left == NULL || T->right == NULL) { node* t = T; if (T->left == NULL) { T = T->right; } else { T = T->left; } delete t; } else { if (T->left->fix < T->right->fix) { rotate_right(T); erase(T->right, val); } else { rotate_left(T); erase(T->left, val); } } } else if (val < T->val) { erase(T->left, val); } else { erase(T->right, val); } } bool exist(node* &T, type val) { if (T == NULL) { return false; } else if (T->val == val) { return true; } else if (val < T->val) { return exist(T->left, val); } else { return exist(T->right, val); } } void clear(node* &T) { if (T == NULL) return; clear(T->left); clear(T->right); delete T; T = NULL; } bool query(node* &root, node* &T) { if (T == NULL) return true; return exist(root, T->val) && query(root, T->left) && query(root, T->right); } int main() { int n; type x; node* T1 = NULL, *T2 = NULL; while (~scanf(" %d", &n)) { for (int i = 0; i < n; ++i) { scanf(" %d", &x); insert(T1, x); } for (int i = 0; i < n; ++i) { scanf(" %d", &x); insert(T2, x); } puts(query(T1, T2) && query(T2, T1) ? "YES" : "NO"); clear(T1); clear(T2); } return 0; }