poj 2104 Kth Number(可持久化线段树)

　　这是我第二次写这题了，原因只前两天看了可持久化数据结构的论文，看到线段树用可持久化的方式来写可以完成这题，于是在我构思好以后就一气呵成的把这题打了出来。一打出来就顺利通过了编译，不过刚开始的时候忘记将新建的结点的两个指针都赋值，所以稍稍debug了一下这个小问题。交上去以后RE了几次，原因是我的hash写烂了。在我改过来以后又变成TLE了，于是我就改成了模拟分配内存。。。。。几经周折，终于AC了！

　　这个题感觉如果是用可持久化来写，思路比较容易理清，不用像划分树复杂的位置运算，也不用像树套树那样动则200行代码。

代码如下：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 #include <cassert>
  6 
  7 using namespace std;
  8 
  9 const int maxn = 100005;
 10 const int HASH = 0x55555555;
 11 const int hashSize = 400009;
 12 
 13 int hash[hashSize], hashPos[hashSize];
 14 
 15 void initHash() {
 16     memset(hashPos, -1, sizeof(hashPos));
 17 }
 18 
 19 void insHash(int x, int pos) {
 20     int p = (x ^ HASH) % hashSize;
 21 
 22     if (p < 0) p += hashSize;
 23     while (hash[p] != x && ~hashPos[p]) {
 24         p = (p + 1) % hashSize;
 25     }
 26 
 27     hash[p] = x;
 28     hashPos[p] = pos;
 29 }
 30 
 31 int getPos(int x) {
 32     int p = (x ^ HASH) % hashSize;
 33 
 34     if (p < 0) p += hashSize;
 35     while (hash[p] != x && ~hashPos[p]) {
 36         p = (p + 1) % hashSize;
 37     }
 38 
 39     return hashPos[p];
 40 }
 41 
 42 int buf[maxn], num[maxn];
 43 int cntNode;
 44 struct Node {
 45     int cnt;
 46 //    Node *left, *right;
 47     int left, right;
 48 
 49     Node(int _cnt = 0) {
 50         cnt = _cnt;
 51 //        left = right = NULL;
 52         left = right = 0;
 53     }
 54 //} *Root[maxn], *Null;
 55 } node[maxn << 5];
 56 int Root[maxn];
 57 
 58 
 59 void input(int n) {
 60     memset(Root, 0, sizeof(Root));
 61     cntNode = 0;
 62 //    Null = new Node();
 63     node[0] = Node();
 64     for (int i = 1; i <= n; i++) {
 65         scanf("%d", &buf[i]);
 66         num[i] = buf[i];
 67     }
 68     sort(num + 1, num + n + 1);
 69 
 70     initHash();
 71     for (int i = 1; i <= n; i++) {
 72         insHash(num[i], i);
 73     }
 74 }
 75 
 76 //void up(Node *rt) {
 77 void up(int rt) {
 78 //    rt->cnt = rt->left->cnt + rt->right->cnt;
 79     node[rt].cnt = node[node[rt].left].cnt + node[node[rt].right].cnt;
 80 }
 81 
 82 //#define lson l, m, rt->left
 83 //#define rson m + 1, r, rt->right
 84 #define lson l, m, node[rt].left
 85 #define rson m + 1, r, node[rt].right
 86 
 87 //void build(int l, int r, Node *&rt) {
 88 void build(int l, int r, int &rt) {
 89 //    rt = new Node();
 90     rt = ++cntNode;
 91     node[rt] = Node();
 92     if (l == r) {
 93 //        rt->left = rt->right = Null;
 94         return ;
 95     }
 96     int m = (l + r) >> 1;
 97 
 98     build(lson);
 99     build(rson);
100     up(rt);
101 }
102 
103 //void update(int x, int l, int r, Node *rt, Node *&newRt) {
104 void update(int x, int l, int r, int rt, int &newRt) {
105     if (l == r) {
106 //        newRt = new Node(rt->cnt + 1);
107         newRt = ++cntNode;
108         node[newRt] = Node(node[rt].cnt + 1);
109 //        newRt->left =newRt->right = Null;
110 
111         return ;
112     }
113     int m = (l + r) >> 1;
114 
115 //    newRt = new Node();
116     newRt = ++cntNode;
117     node[newRt] = Node();
118 //    puts("???");
119     if (x <= m) {
120 //        update(x, lson, newRt->left);
121 //        newRt->right = rt->right;
122         update(x, lson, node[newRt].left);
123         node[newRt].right = node[rt].right;
124     } else {
125 //        update(x, rson, newRt->right);
126 //        newRt->left = rt->left;
127         update(x, rson, node[newRt].right);
128         node[newRt].left = node[rt].left;
129     }
130     up(newRt);
131 }
132 
133 //#define l2son l, m, rt1->left, rt2->left
134 //#define r2son m + 1, r, rt1->right, rt2->right
135 #define l2son l, m, node[rt1].left, node[rt2].left
136 #define r2son m + 1, r, node[rt1].right, node[rt2].right
137 
138 //int query(int k, int l, int r, Node *rt1, Node *rt2) {
139 int query(int k, int l, int r, int rt1, int rt2) {
140     if (l == r) {
141         return num[l];
142     }
143     int m = (l + r) >> 1;
144 //    int cnt = rt2->left->cnt - rt1->left->cnt;
145     int cnt = node[node[rt2].left].cnt - node[node[rt1].left].cnt;
146 
147 //    assert(0 <= cnt && cnt <= r - l + 1);
148     if (k <= cnt) {
149         return query(k, l2son);
150     } else {
151         return query(k - cnt, r2son);
152     }
153 }
154 
155 int segK(int l, int r, int k, int n) {
156     return query(k, 1, n, Root[l - 1], Root[r]);
157 }
158 /*
159 void printTree(Node *rt) {
160     if (!rt) return ;
161     putchar('(');
162     printTree(rt->left);
163     printf("%d", rt->cnt);
164     printTree(rt->right);
165     putchar(')');
166 }
167 */
168 int main() {
169     int n, m;
170 
171 //    freopen("in", "r", stdin);
172     while (~scanf("%d%d", &n, &m)) {
173         input(n);
174         build(1, n, Root[0]);
175         for (int i = 1; i <= n; i++) {
176             update(getPos(buf[i]), 1, n, Root[i - 1], Root[i]);
177 //            printTree(Root[i]);
178 //            puts("~~~");
179         }
180         while (m--) {
181             int l, r, k;
182 
183             scanf("%d%d%d", &l, &r, &k);
184             printf("%d\n", segK(l, r, k, n));
185         }
186     }
187 
188     return 0;
189 }

——written by Lyon