poj 2201 Cartesian Tree

　　正如题目所说，这是笛卡尔树的构造，输出每个结点的父节点，左右子结点的标号。十分简单的题，轻松1y！
View Code
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cassert>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 #include <vector>
  7 
  8 using namespace std;
  9 typedef vector<int> vi;
 10 typedef pair<int, int> pii;
 11 typedef pair<pii, int> piii;
 12 typedef vector<piii> vpiii;
 13 
 14 const int maxn = 50001;
 15 
 16 struct Node{
 17     int key, fix;
 18     int id;
 19     int child[2], parent;
 20     Node(int _key = 0, int _fix = 0, int _id = 0){
 21         child[0] = child[1] = parent = 0;
 22         key = _key;
 23         fix = _fix;
 24         id = _id;
 25     }
 26 }node[maxn];
 27 
 28 struct Cartesian{
 29     int root, back;
 30     Cartesian(){
 31         root = back = 0;
 32     }
 33 
 34     void pushBack(int x){
 35         int p = back;
 36 
 37         while (p && node[p].fix > node[x].fix){
 38             p = node[p].parent;
 39         }
 40         if (p){
 41             if (node[p].child[false]) node[node[p].child[false]].parent = x;
 42             node[x].child[true] = node[p].child[false];
 43             node[x].parent = p;
 44             node[p].child[false] = x;
 45         }
 46         else{
 47             if (root) node[root].parent = x;
 48             node[x].child[true] = root;
 49             root = x;
 50         }
 51         back = x;
 52     }
 53 
 54     void print(int T){
 55         if (!T) return ;
 56         printf("%d : left %d right %d parent %d key %d id %d\n", T, node[T].child[1], node[T].child[0], node[T].parent, node[T].key, node[T].id);
 57         print(node[T].child[1]);
 58         print(node[T].child[0]);
 59     }
 60 }cart;
 61 
 62 vpiii buf;
 63 int mark[maxn];
 64 
 65 void deal(int n){
 66     sort(buf.begin(), buf.end());
 67     cart = Cartesian();
 68 
 69     int size = buf.size();
 70 
 71     for (int i = 0; i < size; i++){
 72         node[i + 1] = Node(buf[i].first.first, buf[i].first.second, buf[i].second);
 73         cart.pushBack(i + 1);
 74 //        cart.print(cart.root);
 75 //        puts("!!!end");
 76     }
 77     for (int i = 1; i <= n; i++){
 78         mark[node[i].id] = i;
 79     }
 80 
 81 
 82     for (int i = 1; i <= n; i++){
 83         printf("%d %d %d\n", node[node[mark[i]].parent].id, node[node[mark[i]].child[1]].id, node[node[mark[i]].child[0]].id);
 84     }
 85 }
 86 
 87 int main(){
 88     int n;
 89     int key, fix;
 90 
 91     while (~scanf("%d", &n)){
 92         buf.clear();
 93         puts("YES");
 94         for (int i = 0; i < n; i++){
 95             scanf("%d%d", &key, &fix);
 96             buf.push_back(make_pair(make_pair(key, fix), i + 1));
 97         }
 98         deal(n);
 99     }
100 
101     return 0;
102 }
——written by Lyon