题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=4325
Description
Input
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, Ti].
In the next M lines, each line contains an integer T i, means the time of i-th query.
Output
Sample outputs are available for more details.
Sample Input
1 1
5 10
4
2 3
1 4
4 8
1
4
6
Sample Output
题意：有n种花，给了这n种花的花期时间，Si~Ti,求在某一时间t，有多少种花正在开放。
思路：这题给的花期时间数据为1~10^9，无法开辟这么大的数组，不能直接建树，必须先将数据进行离散化。离散化：在百科上看到一句很好的话：“离散化就是把连续的量，变成离散的量即变成一个一个的值”，例如区间（1,100）由于这是一个实数区间，其中间的值有无数个，如果我们能把它变为1到100内的整数，这样这些数就变成了有限个，即离散了； ，我们将每个区间的端点都存到一个数组中，然后将这些端点，按照从小到大排列（之后要去除这个数组中重复的点），并建立为与其下标的映射，然后用其下标建树，因为我们只是使用了需要的空间，并没有在整个空间上建树，这样就大大节省了空间和时间，如题中第二个例子，我们将所有数据按照从小到大排列后为1 2 3 4 6 8 分别对应下标1 2 3 4 5 6，此题数据小我们看不出明显的差别，但是如果数据中有区间（1000,10000），那差别马上就出来了，比如我们把题中的区间（4,8）换做（1000,10000）那么如果采用离散化思想，我们还是先排列大小 1 2 3 6 1000 10000对应下标1 2 3 4 5 6，我们只需建一棵根为6的树即可，如果不用离散化，我们就需要建造根为10000的树，大大浪费了空间。
然而！！！我发现同学他们的代码没有使用离散化，而是开辟了150000的空间就过了，很明显测试数据没有很大，都在150000以内，唉！所以可以不用离散化。
方法一：使用树状数组，若花期为t1~t2,更新t1-1及t1-1以下的子树根节点都减一，更新t2及t2以下的子树根节点加一，若求x时刻有多少种花正开着，将x及上方一路节点均相加，最后的和即是结果。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define N 152005
using namespace std;
int c[N]; int Lowbit(int t)
{ ///设k为t末尾0的个数，则求得为2^k=t&(t^(t-1))；
return t&(t^(t-));
}
void update(int x,int t)
{
while(x > )
{
c[x]+=t;
x -= Lowbit(x);
}
}
int sum(int li)
{
int sum=;
while(li<=N)
{
sum+=c[li];
li=li+Lowbit(li);
}
return sum;
} int main()
{
int T;
int n,M,t1,t2,x,Case=;
scanf("%d",&T);
while(T--)
{
memset(c,,sizeof(c));
scanf("%d%d",&n,&M);
while(n--)
{
scanf("%d%d",&t1,&t2);
update(t1-,-);
update(t2,);
}
printf("Case #%d:\n",Case++);
while(M--)
{
scanf("%d",&x);
printf("%d\n",sum(x));
}
}
return ;
}
方法二：使用线段树进行区间更新。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int Max=;
int N,M;
int c[Max]; struct Node
{
int l,r;
int cnt;
}node[*Max]; void build(int L,int R,int i)
{
node[i].l=L;
node[i].r=R;
node[i].cnt=;
if(L==R) return;
int mid=(L+R)/;
build(L,mid,*i);
build(mid+,R,*i+);
} int update(int t1,int t2,int i)
{
if(node[i].l==t1&&node[i].r==t2)
{
node[i].cnt++;
return ;
}
int mid=(node[i].l+node[i].r)/;
if(t2<=mid) update(t1,t2,*i);
else if(t1>mid) update(t1,t2,*i+);
else
{
update(t1,mid,*i);
update(mid+,t2,*i+);
}
} int chazhao(int x,int i)
{
int sum=;
if(node[i].l<=x&&node[i].r>=x)
sum+=node[i].cnt;
if(node[i].l>x) return ;
if(node[i].r<x) return ;
sum+=chazhao(x,*i);
sum+=chazhao(x,*i+);
return sum;
} int main()
{
int T,t1,t2,Case=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
build(,Max,);
for(int i=;i<=N;i++)
{
scanf("%d%d",&t1,&t2);
update(t1,t2,);
}
for(int i=;i<M;i++)
scanf("%d",&c[i]);
printf("Case #%d:\n",Case++);
for(int i=;i<M;i++)
{
printf("%d\n",chazhao(c[i],));
}
}
return ;
}