Boring CountingTime Limit: 3000ms Memory limit: 65536K有疑问？点这里^_^题目描述
In this problem you are given a number sequence P consisting of N integer and Piis the ithelement in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Piis 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.
示例输入
113 56 9 5 2 3 6 8 7 3 2 5 1 41 13 1 101 13 3 63 6 3 62 8 2 81 9 1 9
示例输出
Case #1:137369
给出n个数，，问范围在[l,r]内，值在[A,B]内的数有多少个
转化为在[l,r]的范围内A是第几大的数，B是第几大的树，这样相减就可以得到结果，但是我们只能求第k大的数，不能找出数是第几个，二分k，用二分找出上下界。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std ;#define maxn 50005int a[maxn] , a_sort[maxn] ;int tree[20][maxn] ;int sum[20][maxn] ;int n , m ;void build(int c,int l,int r){if( l == r ) return ;int mid = (l+r)/2 , m = mid-l+1 ;int pl = l , pr = mid+1 , i ;for(i = l ; i <= mid ; i++){if( a_sort[i] < a_sort[mid] )m– ;}for(i = l ; i <= r ; i++){if( i == l ) sum[c][i] = 0 ;else sum[c][i] = sum[c][i-1] ;if( tree[c][i] == a_sort[mid] ){if( m ){m– ;tree[c+1][pl++] = tree[c][i] ;sum[c][i]++ ;}elsetree[c+1][pr++] = tree[c][i] ;}else if( tree[c][i] < a_sort[mid] ){tree[c+1][pl++] = tree[c][i] ;sum[c][i]++ ;}elsetree[c+1][pr++] = tree[c][i] ;}build(c+1,l,mid) ;build(c+1,mid+1,r) ;return ;}int query(int c,int l,int r,int ql,int qr,int k) {if( l == r ) return tree[c][l] ;int mid = (l+r)/2 , num1 , num2 ;if( l == ql ) {num1 = 0 ;num2 = sum[c][qr] ;}else {num1 = sum[c][ql-1] ;num2 = sum[c][qr] – num1 ;}if( k <= num2 )query(c+1,l,mid,l+num1,l+num1+num2-1,k) ;elsequery(c+1,mid+1,r,mid+1+(ql-l-num1),mid+1+(qr-l-num1-num2),k-num2) ;}void solve(int l,int r,int A,int B) {int low , mid , high , last , x ;int ans = 0 , flag = 0 ;low = 1 ; high = r-l+1 ; last = -1 ;while( low <= high ) {mid = (low+high)/2 ;x = query(0,1,n,l,r,mid) ;if( x <= B ) {last = mid ;low = mid + 1 ;}elsehigh = mid – 1 ;}if( last == -1 )flag = 1 ;elseans += last ;low = 1 ; high = r-l+1 ; last = -1 ;while( low <= high ) {mid = (low+high)/2 ;x = query(0,1,n,l,r,mid) ;if( x >= A ) {last = mid ;high = mid – 1 ;}elselow = mid + 1 ;}if( last == -1 )flag = 1 ;elseans = ans – last+1 ;if( flag ) ans = 0 ;printf("%d\n", ans) ;}int main(){int t , step = 0 ;int l , r , A , B ;int i ;scanf("%d", &t) ;while( t– ){scanf("%d %d", &n, &m) ;for(i = 1 ; i <= n ; i++){scanf("%d", &a[i]) ;tree[0][i] = a_sort[i] = a[i] ;}sort(a_sort+1,a_sort+1+n) ;build(0,1,n) ;printf("Case #%d:\n", ++step) ;while( m– ) {scanf("%d %d %d %d", &l, &r, &A, &B) ;solve(l,r,A,B) ;}}return 0 ;}
松树亭亭玉立的耸立在周围小草小花的中间，
