HDU4325--Flowers--树状数组,离散化

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

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

很简单的一道树状数组的改段求点的模版题,基本思想是:tree[]为树状数组,N个元素,tree[i]存放的是i至N被加了多少,

所以,修改[l,r]区间值的操作就变为了,
update(l,1);
update(r+1,-1);

查询某点的操作就变为了查询此点的前缀和

需要注意的是,此题目的数据范围太大,需要进行离散化1 <= S i <= T i <= 10^9(关于离散化,会再写一篇博客)

#include<iostream>
#include<string.h>
#include<vector>
#include<stdio.h>
#include<map>
using namespace std;
const int M=100100;
int tree[M];
int q[M];
int N=0;
map<int,int> ls;
struct node
{
    int le;
    int ri;
}a[M];
int lowbits(int x)
{
    return x&(-x);
}
void update(int i,int val)
{
    for(;i<=N;i+=lowbits(i)){
        tree[i]+=val;
    }
}
int getsum(int i)
{
    int sum=0;
    for(;i>0;i-=lowbits(i)){
        sum+=tree[i];
    }
    return sum;
}
void init()
{
    memset(tree,0,sizeof(tree));
    ls.clear();
}
int main()
{
    freopen("data.in","r",stdin);
    int m,n;
    int t;
    int l,r;
    int tem;
    int casn=1;
    cin>>t;
    while(t--){
        cout<<"Case #"<<casn++<<":"<<endl;
        init();
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>l>>r;
            if(ls.find(l)==ls.end()) ls.insert(make_pair(l,1));
            if(ls.find(r)==ls.end()) ls.insert(make_pair(r,1));
            a[i].le=l;a[i].ri=r;
        }
        for(int i=0;i<m;i++){
            cin>>l;
            if(ls.find(l)==ls.end()) ls.insert(make_pair(l,1));
            q[i]=l;
        }
        int i=1;
        for(map<int,int>::iterator ite=ls.begin();ite!=ls.end();ite++){
            ite->second=i++;
        }
        N=i-1;
        for(int i=0;i<n;i++){
            update(ls[a[i].le],1);
            update(ls[a[i].ri]+1,-1);
        }
        for(int i=0;i<m;i++){
            cout<<getsum(ls[q[i]])<<endl;
        }
    }
}