【转】POJ 2104 归并排序树 二分查找

1. 二分查找容易死循环，注意 (low+high+1 )/2 ， 以及 mid = high-1 或者 mid = low+1

2. 最小或者最大等极限情况要做特殊处理

3.手工调试程序结束后一定要删除检测语句

思路： 用线段树记录归并排序的过程，那么

（1）可以在log(n)时间内查找到 任意数c 在区间(i,j)之间的 名次， 也就是区间内比c小的数的个数+1，

（2）从而我们可以通过二分x来找到在区间(i,j)排名为k的数，注意满足此条件的数可能不止一个，举例 区间数列为

{3, 7,7, 5} k=4

那么满足排名3为的数有5,6,7， 显然我们要找的是7

（1）过程的也需要二分查找，只需要记录比c小的数的个数就可以了

1. /*
2. PROG:
3. LANG: C++
4. ID: heben991
5. */
6. // algorihm:
7. #include <iostream>
8. #include <algorithm>
9. #include <vector>
10. #include <string>
11. #include <cctype>
12. #include <queue>
13. /*
14. #include <list>
15. #include <stack>
16. #include <set>
17. #include <map>
18. #include <cmath>
19. */
20. usingnamespace std;
21. #define ma(a,b) (a)>(b)?(a):(b)
22. #define mi(a,b) (a)<(b)?(a):(b)
23. #define FF(i,a,b) for(int i=(a);i<=(b);i++)
24. #define RR(i,b) for(int i=(0);i<(b);i++)
25. #define clr(x) memset(x,0,sizeof(x))
26. #define pb push_back
27. #define mp make_pair
28. #define sz size()
29. #define F first
30. #define S second
31. #define vv vector
32. #define ii iterator
33. /*
34. #include <sstream>
35. #include <iterator>
36. #define ssm stringstream
37. */
38. #define cn continue
39. #define br break
40. typedefint type;
41. constint ST = 0;
42. #define out(x) cout << #x << "=" << x << endl
43. template <class T> void show(T a, int n) { for (int i = ST; i < ST+n; i++) { cout<<a[i]<<' '; } cout<<endl; }
44. template <class T> void show(T a, int r, int l) { for (int i = ST; i < ST+r; i++) show(a[i], l); cout<<endl; }
45. constint N=110000;
46. struct node
47. {
48. int l,r;
49. };
50. node seg[4*N];
51. int n, m;
52. int a[N], b[25][N];
53. void build(int root, int x, int y, int dep)
54. {
55. int len=y-x+1;
56. int mid=(x+y)/2;
57. seg[root].l = x;
58. seg[root].r = y;
59. if(len>1)
60. {
61. build(root*2,x,mid, dep+1);
62. build(root*2+1,mid+1,y, dep+1);
63. int i=x, j=mid+1,k=x;
64. while(i<=mid || j<=y)
65. {
66. if(j>y || (i<=mid && b[dep+1][i]<=b[dep+1][j] ) )
67. {
68. b[dep][k++] = b[dep+1][i++];
69. }
70. else
71. {
72. b[dep][k++] = b[dep+1][j++];
73. }
74. }
75. }
76. else
77. {
78. b[dep][x] = a[x];
79. }
80. }
81. int query(int root, int c, int x, int y, int dep)
82. {
83. int len=seg[root].r-seg[root].l+1;
84. int mid=(seg[root].l+seg[root].r)/2;
85. if(x<=seg[root].l && y>=seg[root].r)
86. {
87. int low=seg[root].l, high=seg[root].r, mid;
88. if(c <= b[dep][low])return 0;
89. if(c > b[dep][high])return len;
90. while(low < high)
91. {
92. mid = (low+high+1)/2;
93. if(b[dep][mid] >= c) high=mid-1;
94. else low=mid;
95. }
96. return low-seg[root].l+1;
97. }
98. else
99. {
100. int ret=0;
101. if(x<=mid)ret += query(root*2,c,x,y,dep+1);
102. if(y>mid)ret += query(root*2+1,c,x,y,dep+1);
103. return ret;
104. }
105. }
106. int main()
107. {
108. scanf("%d%d", &n, &m);
109. for(int i=1;i<=n;i++) scanf("%d", &a[i]);
110. build(1,1,n,1);
111. //show(b[1], n+1);
112. while(m--)
113. {
114. int i, j, k, low, hig, mid, num;
115. scanf("%d%d%d", &i, &j, &k);
116. low = 1;
117. hig = n;
118. while(low < hig)
119. {
120. mid = (low+hig+1)/2; // hint +1
121. num = query(1, b[1][mid], i, j, 1);
122. if(num >= k) hig = mid-1;
123. else low=mid;
124. }
125. printf("%d\n", b[1][low]);
126. }
127. return 0;
128. }