POJ 2761-Feed the dogs（划分树）求区间内第k小的数

小灰灰 2022-08-21 14:57 124阅读 0赞

# Feed the dogs #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 6000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 17679</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 5561</td> 
  </tr> 
 </tbody> 
</table>

Description

Wind loves pretty dogs very much, and she has n pet dogs. So Jiajia has to feed the dogs every day for Wind. Jiajia loves Wind, but not the dogs, so Jiajia use a special way to feed the dogs. At lunchtime, the dogs will stand on one line, numbered from 1 to n, the leftmost one is 1, the second one is 2, and so on. In each feeding, Jiajia choose an inteval\[i,j\], select the k-th pretty dog to feed. Of course Jiajia has his own way of deciding the pretty value of each dog. It should be noted that Jiajia do not want to feed any position too much, because it may cause some death of dogs. If so, Wind will be angry and the aftereffect will be serious. Hence any feeding inteval will not contain another completely, though the intervals may intersect with each other.  
  
Your task is to help Jiajia calculate which dog ate the food after each feeding.

Input

The first line contains n and m, indicates the number of dogs and the number of feedings.  
  
The second line contains n integers, describe the pretty value of each dog from left to right. You should notice that the dog with lower pretty value is prettier.  
  
Each of following m lines contain three integer i,j,k, it means that Jiajia feed the k-th pretty dog in this feeding.  
  
You can assume that n<100001 and m<50001.

Output

Output file has m lines. The i-th line should contain the pretty value of the dog who got the food in the i-th feeding.

Sample Input

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

Sample Output

3
    2

Source

[POJ Monthly--2006.02.26][],zgl & twb

### 求区间内第k小的数。 ###

和划分树经典的[POJ 2104][]简直是一道题，直接复制代码交上去就AC了。。

/*
    * 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;
    }

[POJ Monthly--2006.02.26]: http://poj.org/searchproblem?field=source&key=POJ+Monthly--2006.02.26
[POJ 2104]: http://blog.csdn.net/mikasa3/article/details/51160021