Flowers
http://acm.hdu.edu.cn/showproblem.php?pid=4325
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.
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 Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, means the time of i-th query.
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 Si and Ti (1 <= Si <= Ti <= 10^9), means i-th flower will be blooming at time [Si, Ti].
In the next M lines, each line contains an integer Ti, 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 outputs are available for more details.
Sample Input
2 1 1 5 10 4 2 3 1 4 4 8 1 4 6
Sample Output
Case #1: 0 Case #2: 1 2 1
题意：给出花开放和凋谢的时间点，询问在一个时间点上有多少花同时开放。
题解：成段更新，单点查询的线段树，就是花开谢时间要hash处理，不然必然超内存。就是这个hash处理个人觉得我做的有点麻烦了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 100005
struct node
{
int s,t;
}num[MAX];
int bloom[MAX<<2];
int add[MAX<<2];
void build(int l,int r,int idx)
{
add[idx]=0;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,idx<<1);
build(mid+1,r,idx<<1|1);
}
int binarySearch(int x,int n)
{
int l=0,r=n-1,mid;
for(;l<=r;)
{
mid=(l+r)>>1;
if(x<bloom[mid])
r=mid-1;
else if(x==bloom[mid])
return mid;
else
l=mid+1;
}
return l;
}
void push_down(int l,int r,int idx)
{
if(add[idx])
{
add[idx<<1]+=add[idx];
add[idx<<1|1]+=add[idx];
add[idx]=0;
}
}
void update(int a,int b,int l,int r,int idx)
{
if(a<=l&&r<=b)
{
add[idx]++;
return;
}
push_down(l,r,idx);
int mid=(l+r)>>1;
if(a<=mid) update(a,b,l,mid,idx<<1);
if(b>mid) update(a,b,mid+1,r,idx<<1|1);
}
int query(int x,int l,int r,int idx)
{
if(l==x&&x==r)
return add[idx];
push_down(l,r,idx);
int mid=(l+r)>>1;
if(x<=mid) return query(x,l,mid,idx<<1);
else return query(x,mid+1,r,idx<<1|1);
}
int main()
{
int ti,n,m,cnt,ans;
scanf("%d",&ti);
for(int cas=1;cas<=ti;++cas)
{
cnt=1;
printf("Case #%d:\n",cas);
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i)
{
scanf("%d%d",&num[i].s,&num[i].t);
bloom[cnt++]=num[i].s;
bloom[cnt++]=num[i].t;
}
//以下就是hash处理，就是把时间点的-1和+1都补上
bloom[0]=0;
sort(bloom,bloom+cnt);
ans=1;
for(int i=1;i<cnt;++i)
if(bloom[i]!=bloom[i-1]) bloom[ans++]=bloom[i];
for(int i=ans-1;i>0;--i)
if(bloom[i]!=bloom[i-1]+1) bloom[ans++]=bloom[i-1]+1;
sort(bloom,bloom+ans);
for(int i=ans;i>0;--i)
if(bloom[i]!=bloom[i-1]+1) bloom[ans++]=bloom[i]-1;
sort(bloom,bloom+ans);
//hash处理完毕
build(0,ans,1);
for(int i=0;i<n;++i)
update(binarySearch(num[i].s,ans),binarySearch(num[i].t,ans),0,ans,1);
for(;m--;)
{
scanf("%d",&cnt);
int pos=binarySearch(cnt,ans);
printf("%d\n",query(pos,0,ans,1));
}
}
return 0;
}