首页 > 代码库 > HDU4325 树状数组

HDU4325 树状数组

2024-08-13 14:05:13   220人阅读

Flowers

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3148    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
 题意：
给出若干个花的开花时期，问某一个日期有几多花开放。
代码：
 1 /*树状数组模板题，若在区间a,b内开花则从a开始向上+1，从b开始向上-1，最后输出 2 某一点的值即可。*/ 3 #include<iostream> 4 #include<string> 5 #include<cstdio> 6 #include<cmath> 7 #include<cstring> 8 #include<algorithm> 9 #include<vector>10 #include<iomanip>11 #include<queue>12 #include<stack>13 using namespace std;14 int t,n,m;15 int A[100005];16 int lowbit(int x)17 {18     return x&(-x);19 }20 void add(int rt,int c)21 {22     while(rt<=100005)23     {24         A[rt]+=c;25         rt+=lowbit(rt);26     }27 }28 int sum(int rt)29 {30     int s=0;31     while(rt>0)32     {33         s+=A[rt];34         rt-=lowbit(rt);35     }36     return s;37 }38 int main()39 {40     int a,b,c;41     scanf("%d",&t);42     for(int i=1;i<=t;i++)43     {44         memset(A,0,sizeof(A));45         printf("Case #%d:\n",i);46         scanf("%d%d",&n,&m);47         while(n--)48         {49             scanf("%d%d",&a,&b);50             add(a,1);51             add(b+1,-1);52         }53         while(m--)54         {55             scanf("%d",&c);56             printf("%d\n",sum(c));57         }58     }59     return 0;60 }

 

HDU4325 树状数组


联系
我们