HDU4417 Super Mario

　　原题传送：http://acm.hdu.edu.cn/showproblem.php?pid=4417

　　划分树 + 二分。

　　总复杂度为mlog(n)log(n)，在O(10^7)左右，可以破了，二分查询区间第k大值，如果该值小于或等于给定高度，那么继续二分。那么最后得到的k值就是所求。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 const int maxn = 100000 + 10;
 5 
 6 int tree[20][maxn], num[20][maxn], a[maxn];
 7 
 8 void build(int l, int r, int d)
 9 {
10     if(l == r) return ;
11     
12     int mid = (l + r) >> 1, saved = 0, save = mid - l + 1;
13     int lp = l, rp = mid + 1;
14     for(int i = l; i <= r; i ++)
15         if(tree[d][i] < a[mid])
16             --save;
17     for(int i = l; i <= r; i ++)
18     {
19         num[d][i] = (i == l ? 0 : num[d][i - 1]);
20         if(tree[d][i] < a[mid] || (saved < save && tree[d][i] == a[mid]))
21         {
22             ++ num[d][i];
23             tree[d + 1][lp++] = tree[d][i];
24             if(tree[d][i] == a[mid]) ++ saved;
25         }
26         else 
27             tree[d + 1][rp++] = tree[d][i];
28     }
29     build(l, mid, d + 1);
30     build(mid + 1, r, d + 1);
31 }
32 
33 int query(int s, int t, int k, int l, int r, int d)
34 {
35     if(l == r)
36         return tree[d][s];
37     
38     int mid = (l + r) >> 1;
39     int s1 = num[d][s - 1];
40     int s2 = num[d][t];
41     if(s == l)  // s == l时s-1到了另外的区间去了
42         s1 = 0;
43     
44     if(s2 - s1 >= k)
45         return query(l + s1, l + s2 - 1, k, l, mid, d + 1);
46         
47     int k1 = s - l - s1;
48     int k2 = (t - s + 1) -  (s2 - s1);
49     return query(mid + 1 + k1, mid + k1 + k2, k - (s2 - s1), mid + 1, r, d + 1);
50 }
51 
52 int solve(int s, int t, int h, int n)
53 {
54     int l = 1, r = (t - s) + 2, ans = 0;
55     while(l < r)
56     {
57         int mid = (l + r) >> 1;
58         int tmp = query(s, t, mid, 1, n, 0);
59         if(tmp <= h)
60             ans = mid, l = mid + 1;
61         else
62             r = mid;
63     }
64     return ans;
65 }
66 
67 int main()
68 {
69     int T, n, m, u, v, w;
70     scanf("%d", &T);
71     for(int cas = 1; cas <= T; cas ++)
72     {
73         scanf("%d%d", &n, &m);
74         for(int i = 1; i <= n; i ++)
75         {
76             scanf("%d", &a[i]);
77             tree[0][i] = a[i];
78         }
79         std::sort(a + 1, a + 1 + n);
80         build(1, n, 0);
81         printf("Case %d:\n", cas);
82         while(m --)
83         {
84             scanf("%d%d%d", &u, &v, &w);
85             printf("%d\n", solve(u + 1, v + 1, w, n));
86         }
87     }
88     return 0;
89 }