POJ 2104 K-th Number

时间：2010-12-05 来源：DestinyDesigner

该总结的东西基本上都写在注释里面了，就不再废话了。

POJ 2104 K-th Number(划分树) 1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4
5 #define DEBUG 0
6
7 const int MaxN = 100010;
8 int val[18][MaxN], toLeft[18][MaxN];
9 int srt[MaxN];
10 int M, N;
11
12 struct Node {
13     int l, r;
14 }node[MaxN<<2];
15
16 inline int L(int x) {return (x<<1)+1;}
17 inline int R(int x) {return (x<<1)+2;}
18
19 void build_tree(int s, int e, int cur_row, int id) {
20     node[id].l = s; node[id].r = e;
21     if(s == e)
22         return;
23     int mid = (s+e)>>1;
24     int emN = mid + 1 - s;
25     for(int i = s; i <= e; ++i) {
26         if(val[cur_row][i] < srt[mid])
27             emN--;
28     }
29     int lp = s, rp = mid+1;
30     for(int i = s; i <= e; ++i) {
31         toLeft[cur_row][i] = i!=s?toLeft[cur_row][i-1]:0;
32         if(val[cur_row][i] < srt[mid]) {
33             val[cur_row+1][lp++] = val[cur_row][i];
34             toLeft[cur_row][i]++;
35         }
36         else if(val[cur_row][i] > srt[mid])
37             val[cur_row+1][rp++] = val[cur_row][i];
38         else if(emN) {
39             val[cur_row+1][lp++] = val[cur_row][i];
40             toLeft[cur_row][i]++;
41             emN--;
42         }
43         else
44             val[cur_row+1][rp++] = val[cur_row][i];
45     }
46     build_tree(s, mid, cur_row + 1, L(id));
47     build_tree(mid+1, e, cur_row + 1, R(id));
48 }
49
50 int query(int s, int e, int k, int cur_row, int id) {
51     if(s == e)
52         return val[cur_row][s];
53     int LL = s==node[id].l?0:toLeft[cur_row][s-1];
54     int LI = toLeft[cur_row][e] - LL;
55 #if DEBUG
56     printf("s = %d, e = %d, k = %d\n", s, e, k);
57     printf("LL = %d, LI = %d\n", LL, LI);
58 #endif
59     //int LM = toLeft[cur_row][(node[id].l+node[id].r)>>1];
60     if(k <= LI)
61         return query(node[id].l+LL, node[id].l+LL+LI-1, k, cur_row+1, L(id));
62     int mid = (node[id].l + node[id].r) >> 1;
63     int RL = s - node[id].l - LL;
64     int RI = e + 1 - s - LI;
65 #if DEBUG
66     printf("RL = %d\n", RL);
67 #endif
68     return query(mid+1+RL, mid+1+RL+RI-1, k - LI, cur_row+1, R(id));
69 }
70
71 int main() {
72 #if DEBUG
73     freopen("in.txt", "r", stdin);
74     freopen("out.txt", "w", stdout);
75 #endif
76     while(scanf("%d%d", &N, &M) == 2) {
77         for(int i = 0; i < N; ++i) {
78             scanf("%d", srt+i);
79             val[0][i] = srt[i];
80         }
81         std::sort(srt, srt + N);
82         build_tree(0, N-1, 0, 0);
83         int s, e, k;
84         for(int i = 0; i < M; ++i) {
85             scanf("%d%d%d", &s, &e, &k);
86             printf("%d\n", query(s-1, e-1, k, 0, 0));
87         }
88     }
89     return 0;
90 }
91
92
93

POJ 2104 K-th Number(归并+二分) 1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4
5 using namespace std;
6
7 inline int MID(int s, int e) {return (s+e)>>1;}
8
9 const int MaxN = 100010;
10 int merge_tree[20][MaxN], n, m, dep[MaxN];
11 int u, v, k, flag;
12
13 void Merge(int begin, int end, int d) {
14     if(begin + 1 == end) {
15         merge_tree[d][begin] = merge_tree[0][begin];
16         dep[begin] = d;
17         return;
18     }
19     int Mid = MID(begin, end);
20     Merge(begin, Mid, d + 1);
21     Merge(Mid, end, d + 1);
22     int i, j, k;
23     for(i = begin, j = Mid, k = begin; i != Mid && j != end;) {
24         if(merge_tree[d+1][i] < merge_tree[d+1][j])
25             merge_tree[d][k++] = merge_tree[d+1][i++];
26         else
27             merge_tree[d][k++] = merge_tree[d+1][j++];
28     }
29     if(i != Mid) {
30         for(; i != Mid; ++i) merge_tree[d][k++] = merge_tree[d+1][i];
31     }
32     if(j != end) {
33         for(; j != end; ++j) merge_tree[d][k++] = merge_tree[d+1][j];
34     }
35 }
36
37 int search(int begin, int end, int s, int e, int x, int d) {
38     int Mid;
39     if(s == begin && end == e) {
40         if(x > merge_tree[d][end-1])
41             return end - begin;
42         if(x < merge_tree[d][begin])
43             return 0;
44         int u = begin - 1, v = end;
45         while(u+1 < v) {
46             Mid = MID(u, v);
47             if(merge_tree[d][Mid] <= x) {
48                 if(merge_tree[d][Mid] == x)
49                     flag++;
50                 u = Mid;
51             }
52             else
53                 v = Mid;
54         }
55         return u - begin + 1;
56     }
57     Mid = MID(begin, end);
58     if(s >= Mid)
59         return search(Mid, end, s, e, x, d+1);
60     if(e <= Mid)
61         return search(begin, Mid, s, e, x, d+1);
62     return search(begin, Mid, s, Mid, x, d+1) + search(Mid, end, Mid, e, x, d+1);
63 }
64
65 void work() {
66     int begin = -1, end = n, Mid;
67     while(begin + 1 < end) {
68         Mid = MID(begin, end);
69         flag = 0;
70         int sum = search(0, n, u, v+1, merge_tree[0][Mid], 0);
71         if(flag && sum - flag < k && sum >= k) {
72             printf("%d\n", merge_tree[0][Mid]);
73             return;
74         }
75         else if(sum < k)
76             begin = Mid;
77         else
78             end = Mid;
79     }
80 }
81
82 int main() {
83     while(scanf("%d%d", &n, &m) != EOF) {
84         for(int i = 0; i < n; ++i) scanf("%d", merge_tree[0] + i);
85         Merge(0, n, 0);
86         for(int i = 0; i < m; ++i) {
87             scanf("%d%d%d", &u, &v, &k);
88             u--; v--;
89             work();
90         }
91     }
92     return 0;
93 }
94