poj 2104 K-th Number (划分树)

 1 #include <map>
 2 #include <queue>
 3 #include <cmath>
 4 #include <vector>
 5 #include <string>
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <climits>
 9 #include <iostream>
10 #include <algorithm>
11 #define INF 0x3f3f3f3f
12 using namespace std;
13 const int MAXN = 1e5 + 10;
14 int a, b, k, N, M, Sorted[MAXN], Tree[30][MAXN], Toleft[30][MAXN];
15 
16 void Build(int Lef, int Rig, int dep)
17 {
18     if (Lef == Rig) return;
19     int Mid = (Lef + Rig) >> 1;
20     int Same = Mid - Lef + 1;
21     for (int i = Lef; i <= Rig; ++ i)
22         if (Tree[dep][i] < Sorted[Mid]) -- Same;
23     int Lpos = Lef, Rpos = Mid + 1;
24     for (int i = Lef; i <= Rig; ++ i)
25     {
26         if (Tree[dep][i] < Sorted[Mid])
27             Tree[dep + 1][Lpos ++] = Tree[dep][i];
28         else if (Tree[dep][i] == Sorted[Mid])
29         {
30             Tree[dep + 1][Lpos ++] = Tree[dep][i];
31             -- Same;
32         }
33         else
34             Tree[dep + 1][Rpos ++] = Tree[dep][i];
35         Toleft[dep][i] = Toleft[dep][Lef - 1] + Lpos - Lef;
36     }
37     Build(Lef, Mid, dep + 1);
38     Build(Mid + 1, Rig, dep + 1);
39 }
40 
41 int Query(int Lef, int Rig, int l, int r, int dep, int k)
42 {
43     if (l == r) return Tree[dep][l];
44     int Mid = (Lef + Rig) >> 1;
45     int Cnt = Toleft[dep][r] - Toleft[dep][l - 1];
46     if (Cnt >= k)
47     {
48         int newL = Lef + Toleft[dep][l - 1] - Toleft[dep][Lef - 1];
49         int newR = newL + Cnt - 1;
50         return Query(Lef, Mid, newL, newR, dep + 1, k);
51     }
52     else
53     {
54         int newR = r + Toleft[dep][Rig] - Toleft[dep][r];
55         int newL = newR - (r - l - Cnt);
56         return Query(Mid + 1, Rig, newL, newR, dep + 1, k - Cnt);
57     }
58 }
59 
60 int main()
61 {
62     while (~scanf("%d%d", &N, &M))
63     {
64         for (int i = 1; i <= N; ++ i)
65         {
66             scanf("%d", &Tree[0][i]);
67             Sorted[i] = Tree[0][i];
68         }
69         sort(Sorted + 1, Sorted + 1 + N);
70         Build(1, N, 0);
71         for (int i = 1; i <= M; ++ i)
72         {
73             scanf("%d%d%d", &a, &b, &k);
74             printf("%d\n", Query(1, N, a, b, 0, k));
75         }
76     }
77 }