HDU 4417-Super Mario(划分树-二分查找)

Dear 丶 2022-08-22 00:08 187阅读 0赞

# Super Mario #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 4436 Accepted Submission(s): 2051**

Problem Description

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in \[L, R\] Mario can hit if the maximal height he can jump is H.

Input

The first line follows an integer T, the number of test data.  
For each test data:  
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.  
Next line contains n integers, the height of each brick, the range is \[0, 1000000000\].  
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.

Sample Input

1
    10 10
    0 5 2 7 5 4 3 8 7 7 
    2 8 6
    3 5 0
    1 3 1
    1 9 4
    0 1 0
    3 5 5
    5 5 1
    4 6 3
    1 5 7
    5 7 3

Sample Output

Case 1:
    4
    0
    0
    3
    1
    2
    0
    1
    5
    1

Source

[2012 ACM/ICPC Asia Regional Hangzhou Online ][2012 ACM_ICPC Asia Regional Hangzhou Online]

Recommend

liuyiding | We have carefully selected several similar problems for you: [5679][] [5678][] [5677][] [5676][] [5675][]

## 题目意思： ##

求每组数中，在l~r区间内比h小的数的个数。

## 解题思路： ##

划分树+二分查找。  
直接可以用[山东省第四届ACM大学生程序设计竞赛-Boring Counting ][ACM_-Boring Counting]  
这个代码来改。

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define N 100005
    using namespace std;
    
    int sorted[4*N];   //排序完的数组
    int toleft[40][4*N];   //toleft[i][j]表示第i层从1到k有多少个数分入左边
    int tree[40][4*N];  //表示每层每个位置的值
    int n;
    
    void building(int l,int r,int dep)
    {
        if(l==r)    return;
        int mid = (l+r)>>1;
        int temp = sorted[mid];
        int i,sum=mid-l+1;    //表示等于中间值而且被分入左边的个数
        for(i=l; i<=r; i++)
            if(tree[dep][i]<temp)
                sum--;
        int leftpos = l;
        int rightpos = mid+1;
        for(i=l; i<=r; i++)
        {
            if(tree[dep][i]<temp)  //比中间的数小，分入左边
                tree[dep+1][leftpos++]=tree[dep][i];
            else if(tree[dep][i]==temp&&sum>0)  //等于中间的数值，分入左边，直到sum==0后分到右边
            {
                tree[dep+1][leftpos++]=tree[dep][i];
                sum--;
            }
            else   //右边
                tree[dep+1][rightpos++]=tree[dep][i];
            toleft[dep][i] = toleft[dep][l-1] + leftpos - l;   //从1到i放左边的个数
        }
        building(l,mid,dep+1);
        building(mid+1,r,dep+1);
    }
    
    //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间
    int query(int L,int R,int l,int r,int dep,int k)
    {
        if(l==r) return tree[dep][l];
        int mid = (L+R)>>1;
        int cnt = toleft[dep][r] - toleft[dep][l-1]; //[l,r]中位于左边的个数
        if(cnt>=k)
        {
            int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; //L+要查询的区间前被放在左边的个数
            int newr = newl + cnt - 1;  //左端点加上查询区间会被放在左边的个数
            return query(L,mid,newl,newr,dep+1,k);
        }
        else
        {
            int newr = r + (toleft[dep][R] - toleft[dep][r]);
            int newl = newr - (r-l-cnt);
            return query(mid+1,R,newl,newr,dep+1,k-cnt);
        }
    }
    
    int Search2(int L,int R,int l,int r,int b)
    {
        int ans=0;
        while(l<=r)
        {
            int mid = (l+r)>>1;
            int res = query(1,n,L,R,0,mid);
            if(res>b)  //直到找到最后边的大于b的结果
            {
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }
        if(!ans) return r;
        return ans-1;
    }
    
    
    int main()
    {
        int t,cas = 1;
        scanf("%d",&t);
        while(t--)
        {
            int m;
            scanf("%d%d",&n,&m);
            int i;
            for(i=1; i<=n; i++)
            {
                scanf("%d",&tree[0][i]);
                sorted[i] = tree[0][i];
            }
            sort(sorted+1,sorted+1+n);
            building(1,n,0);
            int l,r,b;
            printf("Case %d:\n",cas++);
            while(m--)
            {
                scanf("%d%d%d",&l,&r,&b);
                ++l,++r;
                int x = 1;
                int y = r-l+1;
                printf("%d\n",Search2(l,r,x,y,b));
            }
        }
        return 0;
    }

注意题目给的时间是1000MS，用结构体的话会超时。。比如下面这个：

#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]; //核心部分，保存每一个元素的左边的元素中位于下一层左子树的个数
    } 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) //在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 t,cnt=0;
        scanf("%d",&t);
        while(t--)
        {
            printf("Case %d:\n",++cnt);
            int n,m,i,a,b,h;
            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,&h);
                ++a,++b;//二分查找 找出h是区间内第几小的数
                int l=0,r=b-a+2;
                while(r-l>1)
                {
                    int mid=(l+r)>>1;
                    if(query(1,n,0,a,b,mid)<=h)
                        l=mid;
                    else r=mid;
                }
                printf("%d\n",l);
            }
        }
        return 0;
    }

[2012 ACM_ICPC Asia Regional Hangzhou Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=2012+ACM%2FICPC+Asia+Regional+Hangzhou+Online&source=1&searchmode=source
[5679]: http://acm.hdu.edu.cn/showproblem.php?pid=5679
[5678]: http://acm.hdu.edu.cn/showproblem.php?pid=5678
[5677]: http://acm.hdu.edu.cn/showproblem.php?pid=5677
[5676]: http://acm.hdu.edu.cn/showproblem.php?pid=5676
[5675]: http://acm.hdu.edu.cn/showproblem.php?pid=5675
[ACM_-Boring Counting]: http://blog.csdn.net/mikasa3/article/details/51339948