sdut 2610:Boring Counting(第四届ACM山东省省赛原题,划分树 + 二分)

By | 2014/05/07

Boring Counting

Time Limit: 3000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描述

    In this problem you are given a number sequence P consisting of N integer and Pi is the ith element in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Pi is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of Pi (L <= i <= R,  A <= Pi <= B).

输入

     In the first line there is an integer T (1 < T <= 50), indicates the number of test cases.
For each case, the first line contains two numbers N and M (1 <= N, M <= 50000), the size of sequence P, the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9), the number sequence P. Then there are M lines, each line contains four number L, R, A, B(1 <= L, R <= n, 1 <= A, B <= 10^9)

输出

    For each case, at first output a line ‘Case #c:’, c is the case number start from 1. Then for each query output a line contains the answer.

示例输入

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

示例输出

Case #1:
13
7
3
6
9

提示

来源

 2013年山东省第四届ACM大学生程序设计竞赛


  划分树 + 二分(据说归并树也可以做)
  题意:给你T组测试数据,每一组测试数据开始有两个整数N和M。分别表示下一行要输入N个整数,后面接着有M行询问,每行询问有4个整数 L,R,A,B,表示在区间 [L,R] 中查找 A<=Pi<=B 的数有多少个,输出数的个数。
  思路
  这道题最直接的思路是对要求的区间排一下序,然后依次判断比较,记录下在范围[A,B]之内的数有多少个,即为结果。但是M即询问的次数范围在[1,50000],如果每询问一次都要排一次序的话,时间消耗过大,所以上来直接pass掉这种思路。
  因为这道题是基于区间查询,所以接下来我很自然的就想到了“线段树”。线段树的每一个节点代表一个区间,节点中存储的值为区间的特定值,在这里我用节点区间中的最大值,最小值,即数值范围,来表示这个特定值。查询的时候,先找到要找的区间,然后递归下去寻找这个区间内的值有多少个是在数值范围内。如果找到这个区间,发现这个区间的最小值都比[A,B]中的上限B要大,或者最大值都比下限A要小。说明这个区间内没有一个是符合要求的,这个节点代表的整个子树就不用找了。如此,会节约不少时间。
  但是线段树的方法也会超时,比赛的时候看到TLE可是苦思冥想了好久,想了各种优化的方法。无奈,还是没能用线段树解出这道题。
  后来比赛结束后查题解,才知道原来还有”划分树”这种神奇的东西。划分树是基于线段树的,但是我感觉它只继承了线段树“基于区间”的特点,其他的感觉我觉得倒没有什么联系。划分树主要是用来解决“区间第k大的数”问题。下面就让我具体的来讲讲如何用划分树解决这道题。
  大家需要先大体了解一下什么是“划分树”,它的作用是“快速求出某一区间内第k大的元素”,例如数列“1,2,3,4,5,6,7,8″,区间[3,6]内第1大的值就是3。
  那么如何用这个特性求出某一区间内数值在[A,B]范围内的数有多少个呢?
  举个例子:数列“1,5,6,3,8,4,4,2”,L,R,A,B分别为3,6,4,7,即在区间[3,6]范围内查找数值在[4,7]的数有多少个。很显然,这里要查找的区间就是”6,3,8,4″,4<=Pi<=7的数有2个。
  用划分树的思路来解决这个问题。先求出这个区间范围内第1大的数是多少,这里是3,拿它和下限 4(A) 来比较,比这个数小,说明不在这个数值范围内。然后求出第2大的数是4,和下限4(A)比较,在这个范围内,记录下它是第几大的数,标记为down,代表 >= 下限A的第一个数是第几大的数,这里为2(第二大的数)。同理,再依次和上限7(B)比较,求出第一个 <= 上限B的数是第几大的数,标记为up,代表 <= 上限B的数是第几大的数,这里为3。这之间包含了多少个数即为要求得的结果,即(up-down+1) 。
  刚才的思路利用划分树顺序查找锁定up和down的值,这样未免会太慢。这道题对速度的要求还是比较高的,所以这里就要用到“二分的思想。什么是二分呢?举个例子,如果查询区间为[1,8],要求数值范围为[3,6]的数有多少个,先求down。可以先用中间那个数来和下限3比较,即用第4大的数和下限比较,如果比下限小,说明个要找的数在第4大的数右边,下一步再用4和8的中间值,即第6大的数和下限比较,最后得到down的值。同理可以求出up的值。这样一来,速度上又进行了一次优化。
  参考资料
  代码(带注释)
#include <iostream>
#include <stdio click this link here now.h>
#include <algorithm>
using namespace std;
#define MAXN 100005
struct Divide_tree{
    int arr[MAXN];  //原数组
    int sorted[MAXN];   //排序后数组
    int sum[20][MAXN];  //记录第i层1~j划分到左子树的元素个数(包括j)
    int dat[20][MAXN];  //记录第i层元素序列
    void build(int c,int L,int R)   //建树,主要是建立sum[][]和dat[][]数组
    {
        int mid = (L+R)>>1;
        int lsame = mid-L+1;    //lsame用来记录和中间值val_mid相等的,且可以分到左孩子的数的个数
                                //简单来说就是可以放入左孩子的,与中间值val_mid相等的数的个数
        int lp=L,rp=mid+1;  //当前节点的左孩子和右孩子存数的起点
        for(int i=L;i<mid;i++)  //获得一开始的lsame
            if(sorted[i]<sorted[mid])
                lsame--;
        for(int i=L;i<=R;i++){  //从前往后遍历一遍,
                                //确定当前节点区间内的所有元素的归属(放在左孩子或者放在右孩子)
            if(i==L) sum[i]=0;
            else sum[i]=sum[i-1];
            if(dat[i]<sorted[mid]){  //当前元素比中间值val_mid小,放入左孩子
                dat[lp++] = dat[i];
                sum[i]++;
            }
            else if(dat[i]>sorted[mid])  //当前元素比中间值val_mid大,放入右孩子
                dat[rp++] = dat[i];
            else{  //当前元素值与中间值val_mid相等,根据lsame数判断放入左孩子还是右孩子
                if(lsame){
                    lsame--;
                    sum[i]++;
                    dat[lp++]=sorted[mid];
                }
                else{
                    dat[rp++]=sorted[mid];
                }
            }
        }
        if(L==R) return ;   //递归出口,遇到叶子节点
        build(c+1,L,mid);   //递归进入左孩子区间
        build(c+1,mid+1,R); //递归进入右孩子区间
    }
    int query(int c,int L,int R,int ql,int qr,int k)
    {
        //c为树的层数,L,R为当前节点的区间范围,ql,qr为查询的区间范围,k为查询范围内第k大的数
        if(L==R)    //递归出口,返回第k大的数
            return dat[L];
        int s;  //记录[L,ql-1]中进入左孩子的元素的个数
        int ss; //记录[ql,qr]中进入左孩子的元素的个数
        int mid=(L+R)>>1;
        if(L==ql){  //端点重合的情况,单独考虑
            s=0;
            ss=sum[qr];
        }
        else {
            s=sum[ql-1];
            ss=sum[qr]-s;
        }
        if(k<=ss)   //左孩子的元素个数大于k个,说明第k大的元素一定在左孩子区间中,到左孩子中查询
            return query(c+1,L,mid,L+s,L+s+ss-1,k);
        else
            return query(c+1,mid+1,R,mid+1+ql-s-L,mid+1+qr-s-ss-L,k-ss);
    }
};
Divide_tree tree;
int L,R,A,B;
int N,M;
int downbearch(int low,int high)    //找到第一个比B小的数是 第几大的数(用划分树)
{
    int mid = (low+high+1)>>1;
    while(low<high){
        if( tree.query(0,1,N,L,R,mid)<=B )  //查询第mid大的数是否比下界B小。
                                //如果mid比B小,说明要找的位置在mid右边,low应该右移,即
            low = mid;
        else //否则,说明要找的位置应该在mid左边,即
            high = mid-1;
        mid = (low+high+1)>>1;
    }
    if( tree.query(0,1,N,L,R,mid)<=B )    //找到了
        return mid;
    else
        return -1;
}
int upbearch(int low,int high)  //找到第一个比A大的数是 第几大的数(用划分树)
{
    int mid = (low+high+1)>>1;
    while(low<high){
        if( tree.query(0,1,N,L,R,mid)>=A )  //查询第mid大的数是否比上界A大。
                                //如果mid比A大,说明要找的位置在mid左边,high应该左移,即
            high = mid;
        else //否则,说明要找的位置应该在mid右边,即
            low = mid+1;
        mid = (low+high)>>1;
    }
    if(tree.query(0,1,N,L,R,mid)>=A )    //找到了
        return mid;
    else
        return -1;
}
int main()
{
    int i,Case,T;
    scanf("%d",&T);
    for(Case=1;Case<=T;Case++){
        scanf("%d%d",&N,&M);
        for(i=1;i<=N;i++){   //输入
            scanf("%d",&tree.arr[i]);
            tree.sorted[i]=tree.dat[0][i]=tree.arr[i];
        }
        sort(tree.sorted+1,tree.sorted+N+1);
        tree.build(0,1,N);
        printf("Case #%d:\n",Case);
        for(i=1;i<=M;i++){
            scanf("%d%d%d%d",&L,&R,&A,&B);
            int up = downbearch(1,R-L+1);
            int down = upbearch(1,R-L+1);
            if(up==-1||down==-1||A>B||L>R)
                printf("0\n");
            else printf("%d\n",up-down+1);
        }
    }
    return 0;
}

Freecode : www.cnblogs.com/yym2013

One thought on “sdut 2610:Boring Counting(第四届ACM山东省省赛原题,划分树 + 二分)

发表评论

电子邮件地址不会被公开。 必填项已用*标注