http://acm.hdu.edu.cn/showproblem.php?pid=1677
题意是，给出一些矩形的长和宽，如果l1<l2且w1<w2，那么矩形2可以套在矩形1外面。问最优的套法下，最后可以剩下多少个矩形。
我想到的一个做法是，利用Treap来对当前最外层矩形是哪些进行维护。首先我们先按照宽（第二关键字）递增排序，如果相同就按长（第一关键字）递增排序。然后在构建出一棵空的Treap，按顺序插入到树中去。对于每一次插入，找到最大的可以被当前矩形覆盖的一个矩形，然后更新成新的矩形。如果找不到这样的矩形，就直接插入当前矩形。最后Treap的大小就是所需的答案。
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <ctime> 6 7 using namespace std; 8 9 typedef pair<int, int> PII; 10 #define MPR make_pair 11 12 struct treapNode { 13 treapNode *c[2]; 14 PII key; 15 int fix, sz; 16 treapNode() {} 17 treapNode(PII k) : key(k) { 18 fix = rand(); 19 sz = 1; 20 c[0] = c[1] = 0; 21 } 22 } ; 23 typedef treapNode TN; 24 25 struct Treap { 26 TN *root; 27 int sz; 28 Treap() { 29 srand(time(0)); 30 root = 0; 31 sz = 0; 32 } 33 void rotate(TN *&rt, bool l) { 34 bool r = !l; 35 TN *p = rt->c[l]; 36 rt->c[l] = p->c[r]; 37 p->c[r] = rt; 38 p->sz = rt->sz; 39 rt->sz = (rt->c[0] ? rt->c[0]->sz : 0) + (rt->c[1] ? rt->c[1]->sz : 0) + 1; 40 rt = p; 41 } 42 void ins(TN *&rt, TN *x) { 43 if (!rt) { 44 rt = x; 45 return ; 46 } 47 rt->sz++; 48 if (x->key < rt->key) { 49 ins(rt->c[0], x); 50 if (rt->c[0]->fix > rt->fix) { 51 rotate(rt, 0); 52 } 53 } else { 54 ins(rt->c[1], x); 55 if (rt->c[1]->fix > rt->fix) { 56 rotate(rt, 1); 57 } 58 } 59 } 60 void ins(PII k) { 61 TN *tmp = new TN(k); 62 sz++; 63 ins(root, tmp); 64 } 65 void delT(TN *&rt) { 66 if (!rt) return ; 67 delT(rt->c[0]); 68 delT(rt->c[1]); 69 delete rt; 70 } 71 void delT() { 72 delT(root); 73 sz = 0; 74 } 75 void del(TN *&rt, PII key) { 76 // cout << "key " << key.first << ' ' << key.second << ' ' << rt->key.first << ' ' << rt->key.second << endl; 77 if (!rt) return ; 78 if (key < rt->key) del(rt->c[0], key); 79 else if (key > rt->key) del(rt->c[1], key); 80 else { 81 // cout << "not root" << endl; 82 if (!rt->c[0] && !rt->c[1]) { 83 delete rt; 84 rt = 0; 85 return ; 86 } else if (!rt->c[0]) { 87 TN *tmp = rt; 88 rt = rt->c[1]; 89 delete tmp; 90 } else if (!rt->c[1]) { 91 TN *tmp = rt; 92 rt = rt->c[0]; 93 delete tmp; 94 } else { 95 // cout << "here" << endl; 96 if (rt->c[0]->fix < rt->c[1]->fix) { 97 rotate(rt, 1); 98 del(rt->c[0], key); 99 } else { 100 rotate(rt, 0); 101 del(rt->c[1], key); 102 } 103 } 104 } 105 rt->sz = (rt->c[0] ? rt->c[0]->sz : 0) + (rt->c[1] ? rt->c[1]->sz : 0) + 1; 106 } 107 void del(PII key) { 108 del(root, key); 109 sz--; 110 } 111 PII find(TN *rt, PII key) { 112 if (!rt) return MPR(-1, -1); 113 if (rt->key.first >= key.first) { 114 return find(rt->c[0], key); 115 } else { 116 PII ret = find(rt->c[1], key); 117 if (ret == MPR(-1, -1)) { 118 if (rt->key.first >= key.first || rt->key.second >= key.second) return find(rt->c[0], key); 119 return rt->key; 120 } 121 return ret; 122 } 123 } 124 PII find(PII key) { 125 return find(root, key); 126 } 127 } ; 128 129 PII rec[22222]; 130 131 bool cmp(PII a, PII b) { 132 if (a.second != b.second) return a.second < b.second; 133 return a.first < b.first; 134 } 135 136 int main() { 137 // freopen("in", "r", stdin); 138 int T, n; 139 cin >> T; 140 while (T-- && cin >> n) { 141 Treap treap = Treap(); 142 for (int i = 0; i < n; i++) { 143 // cin >> rec[i].first >> rec[i].second; 144 scanf("%d%d", &rec[i].first, &rec[i].second); 145 } 146 sort(rec, rec + n, cmp); 147 for (int i = 0; i < n; i++) { 148 // cout << rec[i].first << ' ' << rec[i].second << endl; 149 PII tmp = treap.find(rec[i]); 150 // cout << "tmp " << tmp.first << ' ' << tmp.second << endl; 151 if (tmp == MPR(-1, -1)) { 152 treap.ins(rec[i]); 153 } else { 154 treap.del(tmp); 155 treap.ins(rec[i]); 156 } 157 } 158 cout << treap.sz << endl; 159 // treap.delT(); 160 } 161 return 0; 162 }
——written by Lyon