showproblem.php?pid=4325

Flowers

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

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

1 1

5 10

2 3

1 4

4 8

Sample Output

Case #1:

Case #2:

Author

BJTU

Source

2012 Multi-University Training Contest 3

题意 n朵花 m个时间点第i朵花正在开放的时间是si，ti 问：在第mi个时间点有多少朵花正在开放

解析思路是我们记录每个时间点有多少个花是开放的树状数组可以解决但是数据太大会超时也存不下数据数量还是比较少的所以我们可以离散化一下我们要把m也离散化进去

AC代码

 #include <stdio.h>

 #include <math.h>

 #include <string.h>

 #include <stdlib.h>

 #include <iostream>

 #include <sstream>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <map>

 #include <vector>

 #include <iomanip>

 using namespace std;

 const int maxn = 3e5+;

 const int maxm = 1e4+;

 const int inf = 0x3f3f3f3f;

 const int mod = ;

 const double epx = 1e-;

 typedef long long ll;

 const ll INF = 1e18;

 const double pi = acos(-1.0);

 int c[maxn],rankk[maxn];

 int n,m,t;

 struct node

 {

     int id,x;

     bool operator<(const node &b)const

     {

         return x<b.x;

     }

 }a[maxn];

 int lowbit(int x)

 {

     return x&(-x);

 }

 int getsum(int x)

 {

     int ans=;

     for(int i=x;i>;i-=lowbit(i))

         ans+=c[i];

     return ans;

 }

 void update(int x,int y,int z)

 {

     for(int i=x;i<=y;i+=lowbit(i))

         c[i]+=z;

 }

 int main()

 {

     int kase=;

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

         memset(c,,sizeof(c));

         memset(rankk,,sizeof(rankk));

         int temp=*n+m;

         for(int i=;i<=temp;i++)

         {

             scanf("%d",&a[i].x);

             a[i].id=i;

         }

         sort(a+,a++temp);

         int k=;

         rankk[a[].id]=k;

         for(int i=;i<=temp;i++)

         {

             if(a[i].x==a[i-].x)

                 rankk[a[i].id]=k;

             else

                 rankk[a[i].id]=++k;

         }

         for(int i=;i<*n;i+=)

         {

             update(rankk[i],k,);

             update(rankk[i+]+,k,-);

         }

         printf("Case #%d:\n",kase++);

         for(int i=*n+;i<=temp;i++)

         {

             printf("%d\n",getsum(rankk[i]));

         }

     }

 }

离散化博客 https://blog.csdn.net/xiangaccepted/article/details/73276826

数据比较水不离散化也可以水过去。。

巴特西

HDU4325 树状数组+离散化

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4325

Flowers

最新文章

热门文章