hdu4325 Flowers【树状数组区间更新单点求值离散化】

119 阅读 0 评论 79 点赞

我是靠谱客的博主多情大米，最近开发中收集的这篇文章主要介绍hdu4325 Flowers【树状数组区间更新单点求值离散化】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Problem Description

As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time. But there are too many flowers in the garden, so he wants you to help him.

Input

The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer S _i and T _i (1 <= S _i <= T _i <= 10^9), means i-th flower will be blooming at time [S _i, T _i].
In the next M lines, each line contains an integer T _i, means the time of i-th query.

Output

For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.

Sample Input

Sample Output


Case #1:
0
Case #2:
1
2
1

Author

BJTU

Source

2012 Multi-University Training Contest 3

这个题是刚刚组队赛做的==，和hdu1556color the ball几乎一样，每朵花给出开放时间，询问某时刻有多少花开。只是多了离散化而已。注意修改模板中的“n”

#include <cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
#define maxn 200008
int n,tree[maxn],X[maxn],li[maxn],ri[maxn],nn,m,mm,ma;
int lowbit(int i)
{
return i&(-i);
}
void update(int i,int x)
{
while(i<=ma)
{
tree[i]=tree[i]+x;
i=i+lowbit(i);
}
}
long long query(int n)
{
long long sum=0;
while(n>0)
{
sum+=tree[n];
n=n-lowbit(n);
}
return sum;
}
int Bin(int num,int R)
{
int l=0,r=R-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(X[mid]==num) return mid;
if(X[mid]<num) l=mid+1;
else r=mid-1;
}
}
int q[maxn];
int main()
{
//
freopen("cin.txt","r",stdin);
int t,cas=1;
scanf("%d",&t);
while(t--)
{
nn=0,m=1,mm;
memset(X,0,sizeof(X));
scanf("%d%d",&n,&mm);
for(int i=0;i<n;i++) scanf("%d%d",&li[i],&ri[i]),X[nn++]=li[i],X[nn++]=ri[i];
for(int i=0;i<mm;i++)scanf("%d",&q[i]),X[nn++]=q[i];
sort(X,X+nn);
// for(int i=0;i<nn;i++)printf("x=%d
",X[i]);puts("");
for(int i=1;i<nn;i++)
if(X[i]!=X[i-1]) X[m++]=X[i];
// for(int i=m-1;i>0;i--)if(X[i]-X[i-1]>=1)X[m++]=X[i-1]+1;
sort(X,X+m);
ma=m+1;
//
for(int i=0;i<m;i++)printf("x=%d
",X[i]);puts("");
//
printf("m=%dn",m);
memset(tree,0,sizeof(tree));
for(int i=0;i<n;i++)
{
int l=Bin(li[i],m);
int r=Bin(ri[i],m);
//
printf("l=%d r=%dn",l+1,r+1);
update(l+1,1);
update(r+2,-1);
//
update(li[i],1);update(ri[i]+1,-1);
}
printf("Case #%d:n",cas++);
for(int i=0;i<mm;i++)
{
int qu=Bin(q[i],m);
// printf("qu=%dn",qu+1);
printf("%I64dn",query(qu+1));
}
}
return 0;
}