POJ 2104-K-th Number(划分树)求区间内第k小的数

- 日理万妓 2022-07-28 11:44 137阅读 0赞

# K-th Number #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 20000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 46178</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 15393</td> 
  </tr> 
  <tr> 
   <td colspan="3" align="center" style="color:#0ead00"><strong>Case Time Limit:</strong> 2000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.  
That is, given an array a\[1...n\] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a\[i...j\] segment, if this segment was sorted?"  
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a\[2...5\] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).  
The second line contains n different integer numbers not exceeding 10 9 by their absolute values --- the array for which the answers should be given.  
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a\[i...j\] segment.

Sample Input

7 3
    1 5 2 6 3 7 4
    2 5 3
    4 4 1
    1 7 3

Sample Output

5
    6
    3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

Source

[Northeastern Europe 2004][], Northern Subregion  
  
题目意思：  
给定一串数，求区间\[a,b\]中第k小的数。  
  
知识点：  
注释很详尽，这儿还有划分树：http://blog.csdn.net/mikasa3/article/details/51160062  
这儿有个传送门→[划分树][Link 1]  
  
注意：数组下标从1到N

/*    
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院    
    * All rights reserved.    
    * 文件名称：k.cpp    
    * 作    者：单昕昕    
    * 完成日期：2016年4月15日    
    * 版 本 号：v1.0      
    */
    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    const int maxn = 100005;
    using namespace std;
    int sor[maxn];//借助sort排序的数组
    struct node
    {
        int num[maxn];//当前层的数
        int cnt[maxn];
        //cnt[]数组是划分树的核心部分
        //保存每一个元素的左边的元素中位于下一层左子树的个数
    } tree[40];//40是树的层数
    //建树代码如下
    void buildtree(int l, int r, int d)//d是深度
    {
        if (l == r)//递归出口
        {
            return;
        }
        int mid = (l+r)>>1;//划分左右区间
        int opleft = l, opright = mid+1;//对左右子树的操作位置的初始化
        int same_as_mid = 0;//和sor[mid]相同的数的数目
        //计算在mid左边有多少个和sor[mid]相同的数（包括mid）,都要放到左子树
        for (int i = mid; i > 0; i--)
        {
            if (sor[i] == sor[mid])
                same_as_mid++;
            else
                break;
        }
        int cnt_left = 0;//被划分到左子树的个数
        for (int i = l; i <= r; i++)
        {
            //从l到r开始遍历
            if (tree[d].num[i] < sor[mid])//左
            {
                tree[d+1].num[opleft++] = tree[d].num[i];
                cnt_left++;
                tree[d].cnt[i] = cnt_left;
            }
            else if(tree[d].num[i] == sor[mid] && same_as_mid)
            {
                //相同的都放在左子树
                tree[d+1].num[opleft++] = tree[d].num[i];
                cnt_left++;
                tree[d].cnt[i] = cnt_left;
                same_as_mid--;
            }
            else//右
            {
                tree[d].cnt[i] = cnt_left;
                tree[d+1].num[opright++] = tree[d].num[i];
            }
        }
        //递归建树
        buildtree(l, mid, d+1);
        buildtree(mid+1, r, d+1);
    }
    int query(int l, int r, int d, int ql, int qr, int k)
    //1 n 0 a b k
    //在d层[l,r]的节点里查找[a,b]中的第k小值
    {
        if (l == r)//递归出口
            return tree[d].num[l];
        int mid = (l+r)>>1;
        int sum_in_left;//区间内元素位于下一层左子树的个数
        int left;//[l,ql-1]左边的元素中位于下一层左子树的个数
        if (ql == l)
        {//如果ql是节点的左边界则有cnt[qr]个数进入左子树
            sum_in_left = tree[d].cnt[qr];
            left = 0;
        }
        else
        {//如果ql不是节点的左边界则有cnt[qr]-cnt[ql-1]个数进入了左子树
            sum_in_left = tree[d].cnt[qr] - tree[d].cnt[ql-1];
            left = tree[d].cnt[ql-1];
        }
        if (sum_in_left >= k)
        {//要找的点在左子树
            //确定下一步询问的位置：
            //如果在ql的左边有left个进入左子树
            //那么ql到qr中第一个进入左子树的必定在l+left的位置
            int new_ql = l+left;
            int new_qr = new_ql+sum_in_left-1;
            return query(l, mid, d+1, new_ql, new_qr, k);
        }
        else//要找的点在右子树
        {
            //确定下一步询问的位置
            int a = ql - l - left;//表示当前区间左半部分即[l,ql-1]中在下一层是右孩子的个数 
            int b = qr - ql + 1 - sum_in_left;//表示当前区间右半部分即[ql,qr]中在下一层是右孩子的个数
            int new_ql = mid + a + 1;
            int new_qr = mid + a + b;
            //k-sum_in_left表示要减去区间里已经进入左子树的个数
            return query(mid+1, r, d+1, new_ql, new_qr, k - sum_in_left);
        }
    }
    int main()
    {
        int n,m,i,a,b,k;
        scanf("%d%d",&n,&m);
        for(i=1; i<=n; ++i)
        {
            scanf("%d",&sor[i]);//先插入到sor数组
            tree[0].num[i]=sor[i];//再插入第一层
        }
        sort(sor+1,sor+n+1);//升序排列
        buildtree(1,n,0);//建树
        for(i=1; i<=m; ++i)
        {//查询
            scanf("%d%d%d",&a,&b,&k);
            printf("%d\n",query(1,n,0,a,b,k));
        }
        return 0;
    }

[Northeastern Europe 2004]: http://poj.org/searchproblem?field=source&key=Northeastern+Europe+2004
[Link 1]: http://blog.csdn.net/mikasa3/article/details/51160062