首页 > 代码库 > 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.
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
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(树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。