首页 > 代码库 > HDU 4325 Flowers(树状数组)

HDU 4325 Flowers(树状数组)

Flowers

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3150    Accepted Submission(s): 1549


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 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 Input
21 15 1042 31 44 8146
 

 

Sample Output
Case #1:0Case #2:121
 

 

Author
BJTU
 

 

Source
2012 Multi-University Training Contest 3
 
/*给你每一朵话的开花时间段,询问你某一时刻的开花数量*//*重新定义树状数组的意义,不再是前i个数的和,而是第i个位置的数值*//*明显数据会爆的,我去.....数据太水了*/#include<iostream>#include<string.h>#include<stdio.h>#define N 100010using namespace std;int c[N],T[N];int t;int n,m;int lowbit(int x){    return x&(-x);}void update(int x,int val){    while(x<=N)    {        c[x]+=val;        x+=lowbit(x);    }}int getsum(int x){    int s=0;    while(x>0)    {        s+=c[x];        x-=lowbit(x);    }    return s;}int main(){    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);    scanf("%d",&t);    for(int Case=1;Case<=t;Case++)    {        memset(c,0,sizeof c);        scanf("%d%d",&n,&m);        //cout<<"n="<<n<<" "<<"m="<<m<<endl;        int si,ti;        for(int i=0;i<n;i++)        {            scanf("%d%d",&si,&ti);            //cout<<si<<" "<<ti<<endl;                        update(si,1);                        // for(int j=si;j<=ti;j++)                // update(j,1);            update(ti+1,-1);        }        for(int i=0;i<m;i++)            scanf("%d",&T[i]);        printf("Case #%d:\n",Case);        // for(int i=1;i<10;i++)             // printf("%d\n",getsum(i));        for(int i=0;i<m;i++)        {            //cout<<"T[i]="<<T[i]<<" "<<"T[i]-1="<<T[i]-1<<endl;            printf("%d\n",getsum(T[i]));        }    }}

 

HDU 4325 Flowers(树状数组)