【題目描述】有n個(gè)數(shù)字排成一列，有m個(gè)詢問，格式為：left right k 即問在區(qū)間[left,right]第k大的數(shù)據(jù)為多少？建圖: 建樹的過程比較簡單，對于區(qū)間[l,r]，首先通過對原數(shù)組的排序找到這個(gè)區(qū)間的中位數(shù)a[mid]，小于a[mid]的數(shù)劃入它的左子樹[l,mid-1]，大于它的劃入右子樹[mid,r]。 同時(shí)，對于第i個(gè)數(shù)a[i]，記錄在[l,i]區(qū)間內(nèi)有多少數(shù)被劃入左子樹。最后，對它的左子樹區(qū)間[l,mid-1]和右子樹區(qū)間[mid,r]遞歸的繼續(xù)建樹就可以了。 建樹的時(shí)候要注意，對于被分到同一子樹的元素，元素間的相對位置不能改變。

查找的過程中主要問題就是確定將要查找的區(qū)間。 查找深度為dep，在大區(qū)間[L ,R]中找小區(qū)間[l ,r]中的第k元素。 我們的想法是，先判斷[l ,r]中第k元素在[L ,R]的哪個(gè)子樹中，然后找出對應(yīng)的小區(qū)間和k，遞歸的進(jìn)行查找，直到小區(qū)間的l==r為止。 通過之前的記錄可以知道，在區(qū)間[L,l-1]中有(toleft[dep][l-1]-toleft[dep][L-1])進(jìn)入左子樹， 記它為x。

同理區(qū)間[L,r]中有(toleft[dep][r]-toleft[dep][L-1])個(gè)數(shù)進(jìn)去左子樹，記它為y。 所以，我們知道區(qū)間小區(qū)間[l,r]中有(y-x)個(gè)數(shù)進(jìn)入左子樹。那么如果(y-x)>=k，那么就在左子樹中繼續(xù)查找，否則就在右子樹中繼續(xù)查找。

? 接著，解決查找的小區(qū)間的問題。 ? 如果接下來要查找的是左子樹，那么小區(qū)間應(yīng)該是[L+([L,l-1]區(qū)間進(jìn)入左子樹的個(gè)數(shù)),L+([L,r]區(qū)間內(nèi)進(jìn)入左子樹的個(gè)數(shù))-1]。即區(qū)間[L+x,L+y-1]。 ??? 顯然，這里k不用變。 ? 如果接下來要查找的是右子樹，那么小區(qū)間應(yīng)該是[mid+([L,l-1]區(qū)間中進(jìn)入右子樹的個(gè)數(shù)),mid+([L,r]區(qū)間進(jìn)入右子樹的個(gè)數(shù))-1]。 ??? 即區(qū)間[mid+(l-L-x),mid+(r-L-y)]。 ??? 顯然，這里k要減去區(qū)間里已經(jīng)進(jìn)入左子樹的個(gè)數(shù)，即k變?yōu)閗-(y-x)。
#define MAX_SIZE 100005
int sorted[MAX_SIZE];//已經(jīng)排好序的數(shù)據(jù)
int toleft[25][MAX_SIZE];
int tree[25][MAX_SIZE];
void build_tree(int left, int right, int deep)
{
?int i;
?if (left == right) return ;
?int mid = (left + right) >> 1;
?int same = mid - left + 1; //位于左子樹的數(shù)據(jù)
?for (i = left; i <= right; ++i) {//計(jì)算放于左子樹中與中位數(shù)相等的數(shù)字個(gè)數(shù)
??if (tree[deep][i] < sorted[mid]) {
???--same;
??}
?}
?int ls = left;
?int rs = mid + 1;
?for (i = left; i <= right; ++i) {
??int flag = 0;
??if ((tree[deep][i] < sorted[mid]) || (tree[deep][i] == sorted[mid] && same > 0)) {
???flag = 1;
???tree[deep + 1][ls++] = tree[deep][i];
???if (tree[deep][i] == sorted[mid])
????same--;
??} else {
???tree[deep + 1][rs++] = tree[deep][i];
??}
??toleft[deep][i] = toleft[deep][i - 1]+flag;
?}
?build_tree(left, mid, deep + 1);
?build_tree(mid + 1, right, deep + 1);
}
int query(int left, int right, int k, int L, int R, int deep)
{
?if (left == right)
??return tree[deep][left];
??? int mid = (L + R) >> 1;
?int x = toleft[deep][left - 1] - toleft[deep][L - 1];//位于left左邊的放于左子樹中的數(shù)字個(gè)數(shù)
?int y = toleft[deep][right] - toleft[deep][L - 1];//到right為止位于左子樹的個(gè)數(shù)
?int ry = right - L - y;//到right右邊為止位于右子樹的數(shù)字個(gè)數(shù)
?int cnt = y - x;//[left,right]區(qū)間內(nèi)放到左子樹中的個(gè)數(shù)
?int rx = left - L - x;//left左邊放在右子樹中的數(shù)字個(gè)數(shù)
?if (cnt >= k) {
??//printf("sss %d %d %d\n", xx++, x, y);
??return query(L + x, L + y - 1, k, L, mid, deep + 1);
?}
?else {
??//printf("qqq %d %d %d\n", xx++, x, y);
??return query(mid + rx + 1, mid + 1 + ry, k - cnt, mid + 1, R, deep + 1);
?}
}
int main()
{
?int m, n;
?int a, b, k;
?int i;
?while (scanf("%d%d", &m, &n) == 2) {
??for (i = 1; i <= m; ++i) {
???scanf("%d", &sorted[i]);
???tree[0][i] = sorted[i];
??}
??sort(sorted + 1, sorted + 1 + m);
??build_tree(1, m, 0);
??for (i = 0; i < n; ++i) {
???scanf("%d%d%d", &a, &b, &k);
???printf("%d\n", query(a, b, k, 1, m, 0));
??}
?}
?return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/lzhitian/archive/2012/08/01/2618092.html

總結(jié)

以上是生活随笔為你收集整理的【转】POJ-2104（K-th Number 划分树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。