http://acm.hdu.edu.cn/showproblem.php?pid=2665以前只知道用歸并樹做，查詢時間復雜度要 m * ( log n)^3， 昨天學了一個劃分樹，查詢只要m * logn 。其實這題的正解就是使用劃分樹來做。劃分樹跟歸并樹剛好是相反的操作，劃分樹查詢用于查詢[ l , r ]內第k大的數， 歸并樹用于查詢某個數在[ l , r ]內排第幾。 劃分樹的資料比較少，可以參看 小hh 大牛的blog http://www.notonlysuccess.com/?p=142， 或者下面這個blog http://blog.163.com/tonyshaw@yeah/blog/static/142021718201035102322338/
  hdu 2665
1 #include <cstdio>
2#include <iostream>
3#include <cmath>
4#include <complex>
5#include <algorithm>
6#include <cstring>
7#include <queue>
8using namespace std;
9
10const int maxn = 100020;
11int Left[20][maxn], sorted[maxn], tree[20][maxn];
12
13void build_tree( int L, int R, int v )
14 {
15 int mid = ( L + R ) >> 1;
16 if( L == R ) return;
17 int m = sorted[mid];
18 int same = mid - L + 1; // same表示和m = sorted[mid] 相等且分到左邊的
19 for( int i = L; i <= R; i++ )
20 if( tree[v][i] < m ) same--;
21 int lpos = L;
22 int rpos = mid+1;
23 int ss = 0;
24 for( int i = L; i <= R; i++ )
25  {
26 if( i == L ) Left[v][i] = 0;
27 else Left[v][i] = Left[v][i-1];
28 if( tree[v][i] < m )
29 {
30 tree[v+1][lpos++] = tree[v][i];
31 Left[v][i]++;
32 }
33 else if( tree[v][i] > m )
34 {
35 tree[v+1][rpos++] = tree[v][i];
36 }
37 else
38 {
39 if( ss < same )
40 {
41 tree[v+1][lpos++] = tree[v][i];
42 Left[v][i]++;
43 ss++;
44 }
45 else tree[v+1][rpos++] = tree[v][i];
46 }
47 }
48 build_tree( L, mid, v + 1 );
49 build_tree( mid + 1, R, v + 1 );
50 }
51
52int query( int L, int R, int l, int r, int k, int v )
53{
54 int mid = ( L + R ) >> 1;
55 if( l == r ) return tree[v][l];
56 int off; // off表示 [ L, l-1 ]有多少個分到左邊
57 int cnt; // cnt表示 [ l, r ]有多少個分到左邊
58 if( l == L )
59 {
60 off = 0;
61 cnt = Left[v][r];
62 }
63 else
64 {
65 off = Left[v][l-1];
66 cnt = Left[v][r] - Left[v][l-1];
67 }
68 if( cnt >= k ) //有多于k個分到左邊,顯然去左兒子區間找第k個
69 {
70 int lnew = L + off;
71 int rnew = lnew + cnt - 1;
72 return query( L, mid, lnew, rnew, k, v + 1 );
73 }
74 else
75 {
76 off = l - L - off; // off表示 [ L, l-1 ]有多少個分到右邊
77 k = k - cnt;
78 cnt = r - l + 1 - cnt; // cnt表示 [ l, r ]有多少個分到右邊
79 int lnew = mid + 1 + off;
80 int rnew = lnew + cnt - 1;
81 return query( mid + 1, R, lnew, rnew, k, v + 1 );
82 }
83}
84
85int main(int argc, char *argv[])
86{
87 int t, n, m, l, r, k;
88 scanf("%d",&t);
89 while( t-- )
90 {
91 scanf("%d%d",&n,&m);
92 for( int i = 1; i <= n; i++ )
93 {
94 scanf("%d",&tree[0][i]);
95 sorted[i] = tree[0][i];
96 }
97 sort( sorted + 1, sorted + n + 1 );
98 build_tree( 1, n, 0 );
99 for( int i = 0; i < m; i++ )
100 {
101 scanf("%d%d%d",&l,&r,&k);
102 printf("%d\n",query( 1, n, l, r, k, 0 ) );
103 }
104 }
105 return 0;
106}
107
|