zoj 2243 Binary Search Heap Construction （笛卡尔树）

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1243

　　这时一道笛卡尔树的题目。

　　刚开始，想都没想就手打了一棵Treap，也没有计算最坏情况下要操作多少次，于是就一直改指针什么的，并一直TLE。后来，只好找题解来解释一下我TLE的原因了。直接就看到一个博客，博主也是跟我一样，刚开始的时候用了Treap，结果TLE了。然后，我就看到了一个新名词——笛卡尔树(Cartesian Tree)。我立即维基了一下笛卡尔树的定义，发现原来笛卡尔树的构造十分简单。

　　笛卡尔树，一种特殊的Treap，采用离线插入。当结点权值被固定的时候，Treap没有了随机化，将有变得相当不平衡的状态。这时，如果用Cartesiant Tree算法，可以保证将复杂度限制在O(nlogn)中。首先，将要插入的结点按找key值来排序，这个操作的复杂度视排序方法而定。然后，按顺序插入到树中。注意，这里插入的方法有点不一样，不是用Treap的插入方法，如果用那种方法，算法将退化到O(n^2)。笛卡尔树的插入，是由上一插入的结点开始查找的（鉴于笛卡尔树的特殊性，结点需要指向父节点的指针）。从上一插入的结点开始，向祖先的方向查找到第一个权值(fix)比插入的结点大的结点（这里用的是最大堆），然后就将该结点的右子树（就是刚刚找上来的那边）作为待插入的结点的左子树，然后该节点的右儿子就由新插入的结点来代替。back指针指向这个新插入的结点。这里的复杂度是O(n)。

　　为什么这样的复杂度只有O(n)？

　　因为在最右边的直链的长度最多为n，而且如果插入的结点的fix值比它大，他们将会被转移到左子树，于是搜索的次数不超过n，插入的次数为n，加起来就是O(2*n)，也就是O(n)。然后整体的复杂度就由排序的方式来决定了！

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cassert>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 #include <string>
  7 #include <vector>
  8 
  9 using namespace std;
 10 typedef pair<string, int> psi;
 11 typedef vector<psi> vpsi;
 12 
 13 struct Node {
 14     Node *child[2], *parent;
 15     string key;
 16        int fix;
 17     Node(string _key, int _fix) {
 18         child[0] = child[1] = parent = NULL;
 19         key = _key;
 20         fix = _fix;
 21     }
 22 };
 23 
 24 struct Cartesian {
 25     Node *root, *back;
 26     Cartesian() {
 27         root = back = NULL;
 28     }
 29 
 30     void rotate(Node *rt, bool left){
 31         bool right = !left;
 32         Node *p = rt->child[right];
 33 
 34         p->parent = rt->parent;
 35         if (p->child[left]) p->child[left]->parent = rt;
 36         rt->child[right] = p->child[left];
 37         rt->parent = p-> child[left];
 38         p->child[left] = rt;
 39     }
 40 
 41     void pushBack(Node *x) {
 42         Node *p = back;
 43 
 44         while (p && p->fix < x->fix) p = p->parent;
 45 //printf("insert at %d\n", p);
 46         if (p) {
 47             if (p->child[false]) p->child[false]->parent = x;
 48             x->child[true] = p->child[false];
 49             x->parent = p;
 50             p->child[false] = x;
 51         } else {
 52             if (root) root->parent = x;
 53             x->child[true] = root;
 54             root = x;
 55         }
 56         back = x;
 57     }
 58 
 59     void print(Node *T) {
 60         if (!T) return ;
 61         putchar('(');
 62         print(T->child[true]);
 63         printf("%s/%d", T->key.c_str(), T->fix);
 64         print(T->child[false]);
 65         putchar(')');
 66     }
 67 }cart;
 68 
 69 void deal(int n) {
 70     cart = Cartesian();
 71 
 72     char buf[100];
 73     vpsi tmp;
 74 
 75     while (n--){
 76         scanf("%s", buf);
 77 
 78         int p = 0, key;
 79 
 80         while (buf[p] != '/') p++;
 81         buf[p] = 0;
 82         sscanf(&buf[p + 1], "%d", &key);
 83         tmp.push_back(make_pair(buf, key));
 84     }
 85     sort(tmp.begin(), tmp.end());
 86 
 87     int size = tmp.size();
 88 
 89     for (int i = 0; i < size; i++) {
 90         Node *temp = new Node(tmp[i].first, tmp[i].second);
 91 
 92 //printf("cur %s  %d\n", tmp[i].first.c_str(), tmp[i].second);
 93 //puts("pass");
 94 //printf("back  %d\n", cart.back);
 95         cart.pushBack(temp);
 96 //cart.print(cart.root);
 97 //puts("");
 98     }
 99     cart.print(cart.root);
100     puts("");
101 }
102 
103 int main(){
104     int n;
105 
106 //freopen("in", "r", stdin);
107     while (~scanf("%d", &n) && n){
108         deal(n);
109     }
110 
111     return 0;
112 }

——written by Lyon