SDIBT 3237 Boring Counting( 划分树+二分枚举 )

http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=3237

Problem H:Boring Counting

Time Limit: 3 Sec Memory Limit: 128 MB Submit: 8 Solved: 4 [Submit][Status][Discuss]

Description

In this problem you are given a number sequence P consisting of N integer and P_i is the i^th 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 P_i is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of P_i (L <= i <= R, A <= P_i <= B).

Input

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 P_i(1 <= P_i <= 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)

Output

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.

Sample Input

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

Sample Output

Case #1:
13
7
3
6
9

HINT

Source

山东省第四届ACM程序设计大赛2013.6.9

【题解】：

　　题目大意：求[L,R]区间内的pi在满足[A<=pi<=B]的个数

　　　一开始想得是：直接用线段树记录区间的最大最小值，当最大最小值满足[A<=pi<=B]时就加上整个区间的长度，可是这样做会超时，因为不满足这个条件的情况太多了，基本上不满足的话每次都要遍历到最底层，所以TLE在所难免。

　　后面觉得还是划分树靠谱，不过比赛的时候也没时间写了，划分树是求区间的第K大值，我们要转换一下，就是A和B在区间的分别是第几大，然后用后者减掉前者就是要求的解，那么拿A来说明一下，A在区间中到底是第几大呢，刚说过划分树是求区间的第K大数是谁的，而我们要求的是知道这个数是谁要求他在区间是第几大，有点绕口哈，这里，我们用到二分枚举，枚举区间第K大的数，然后与A进行比较，如果大于等于A，继续向下枚举，直到等于A的最后一个A为止，对于B同理：

时间复杂度，划分树的时间复杂度为O（n*log（n））二分枚举为O(logn) 整体时间复杂度为O(n*log(n)*log(n))

【code】：

  1 /**
  2 Judge Status:Accepted   Memory:13260 KB
  3 Time:2500 ms    Language:C++
  4 Code Lenght:2824 B  Author:cj
  5 */
  6 
  7 #include<iostream>
  8 #include<stdio.h>
  9 #include<string.h>
 10 #include<algorithm>
 11 
 12 #define N 50050
 13 using namespace std;
 14 
 15 int sorted[N];   //排序完的数组
 16 int toleft[30][N];   //toleft[i][j]表示第i层从1到k有多少个数分入左边
 17 int tree[30][N];  //表示每层每个位置的值
 18 int n;
 19 
 20 void building(int l,int r,int dep)
 21 {
 22     if(l==r)    return;
 23     int mid = (l+r)>>1;
 24     int temp = sorted[mid];
 25     int i,sum=mid-l+1;    //表示等于中间值而且被分入左边的个数
 26     for(i=l;i<=r;i++)
 27     {
 28         if(tree[dep][i]<temp)   sum--;
 29     }
 30     int leftpos = l;
 31     int rightpos = mid+1;
 32     for(i=l;i<=r;i++)
 33     {
 34         if(tree[dep][i]<temp)  //比中间的数小，分入左边
 35         {
 36             tree[dep+1][leftpos++]=tree[dep][i];
 37         }
 38         else if(tree[dep][i]==temp&&sum>0)  //等于中间的数值，分入左边，直到sum==0后分到右边
 39         {
 40              tree[dep+1][leftpos++]=tree[dep][i];
 41              sum--;
 42         }
 43         else   //右边
 44         {
 45             tree[dep+1][rightpos++]=tree[dep][i];
 46         }
 47         toleft[dep][i] = toleft[dep][l-1] + leftpos - l;   //从1到i放左边的个数
 48     }
 49     building(l,mid,dep+1);
 50     building(mid+1,r,dep+1);
 51 }
 52 
 53 //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间
 54 int query(int L,int R,int l,int r,int dep,int k)
 55 {
 56     if(l==r)    return tree[dep][l];
 57     int mid = (L+R)>>1;
 58     int cnt = toleft[dep][r] - toleft[dep][l-1]; //[l,r]中位于左边的个数
 59     if(cnt>=k)
 60     {
 61         int newl = L + toleft[dep][l-1] - toleft[dep][L-1]; //L+要查询的区间前被放在左边的个数
 62         int newr = newl + cnt - 1;  //左端点加上查询区间会被放在左边的个数
 63         return query(L,mid,newl,newr,dep+1,k);
 64     }
 65     else
 66     {
 67         int newr = r + (toleft[dep][R] - toleft[dep][r]);
 68         int newl = newr - (r-l-cnt);
 69         return query(mid+1,R,newl,newr,dep+1,k-cnt);
 70     }
 71 }
 72 
 73 int bilibili(int L,int R,int l,int r,int a)  //二分枚举
 74 {
 75     int ans=-1;
 76     while(l<=r)
 77     {
 78         int mid = (l+r)>>1;
 79         int res = query(1,n,L,R,0,mid);
 80         if(res>=a)  //直到找到最左边的那个等于a的结果
 81         {
 82             r = mid - 1;
 83             ans = mid;
 84         }
 85         else
 86         {
 87             l = mid + 1;
 88         }
 89     }
 90     return ans;
 91 }
 92 
 93 int bulobulo(int L,int R,int l,int r,int b)
 94 {
 95     int ans=0;
 96     while(l<=r)
 97     {
 98         int mid = (l+r)>>1;
 99         int res = query(1,n,L,R,0,mid);
100         if(res>b)  //直到找到最后边的大于b的结果
101         {
102             r = mid - 1;
103             ans = mid;
104         }
105         else
106         {
107             l = mid + 1;
108         }
109     }
110     if(!ans)    return r;
111     return ans-1;
112 }
113 
114 
115 int main()
116 {
117     int t,cas = 1;
118     scanf("%d",&t);
119     while(t--)
120     {
121         int m;
122         scanf("%d%d",&n,&m);
123         int i;
124         for(i=1;i<=n;i++)
125         {
126             scanf("%d",&tree[0][i]);
127             sorted[i] = tree[0][i];
128         }
129         sort(sorted+1,sorted+1+n);
130         building(1,n,0);
131         int l,r,a,b;
132         printf("Case #%d:
",cas++);
133         while(m--)
134         {
135             scanf("%d%d%d%d",&l,&r,&a,&b);
136             int x = 1;
137             int y = r-l+1;
138             int cnt1 = bilibili(l,r,x,y,a);
139             int cnt2 = bulobulo(l,r,x,y,b);
140             if(cnt1==-1)
141             {
142                 printf("0
");
143                 continue;
144             }
145             printf("%d
",cnt2-cnt1+1);
146         }
147     }
148     return 0;
149 }