本文主要是介绍sdut2610--Boring Counting(二分+划分树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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, 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
给出n个数，问范围在[l,r]内，值在[A,B]内的数有多少个
转化为在[l,r]的范围内A是第几大的数，B是第几大的树，这样相减就可以得到结果，但是我们只能求第k大的数，不能找出数是第几个，二分k，用二分找出上下界。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define maxn 50005
int 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]++ ;
}
else
tree[c+1][pr++] = tree[c][i] ;
}
else if( tree[c][i] < a_sort[mid] )
{
tree[c+1][pl++] = tree[c][i] ;
sum[c][i]++ ;
}
else
tree[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) ;
else
query(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 ;
}
else
high = mid - 1 ;
}
if( last == -1 )
flag = 1 ;
else
ans += 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 ;
}
else
low = mid + 1 ;
}
if( last == -1 )
flag = 1 ;
else
ans = 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 ;
}
这篇关于sdut2610--Boring Counting(二分+划分树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
