题目网址：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
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-1)); } void update(int x,int t) { while(x > 0) { c[x]+=t; x -= Lowbit(x); } } int sum(int li) { int sum=0; while(li<=N) { sum+=c[li]; li=li+Lowbit(li); } return sum; } int main() { int T; int n,M,t1,t2,x,Case=1; scanf("%d",&T); while(T--) { memset(c,0,sizeof(c)); scanf("%d%d",&n,&M); while(n--) { scanf("%d%d",&t1,&t2); update(t1-1,-1); update(t2,1); } printf("Case #%d: ",Case++); while(M--) { scanf("%d",&x); printf("%d ",sum(x)); } } return 0; }
方法二：使用线段树进行区间更新。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int Max=150005; int N,M; int c[Max]; struct Node { int l,r; int cnt; }node[5*Max]; void build(int L,int R,int i) { node[i].l=L; node[i].r=R; node[i].cnt=0; if(L==R) return; int mid=(L+R)/2; build(L,mid,2*i); build(mid+1,R,2*i+1); } int update(int t1,int t2,int i) { if(node[i].l==t1&&node[i].r==t2) { node[i].cnt++; return 0; } int mid=(node[i].l+node[i].r)/2; if(t2<=mid) update(t1,t2,2*i); else if(t1>mid) update(t1,t2,2*i+1); else { update(t1,mid,2*i); update(mid+1,t2,2*i+1); } } int chazhao(int x,int i) { int sum=0; if(node[i].l<=x&&node[i].r>=x) sum+=node[i].cnt; if(node[i].l>x) return 0; if(node[i].r<x) return 0; sum+=chazhao(x,2*i); sum+=chazhao(x,2*i+1); return sum; } int main() { int T,t1,t2,Case=1; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); build(1,Max,1); for(int i=1;i<=N;i++) { scanf("%d%d",&t1,&t2); update(t1,t2,1); } for(int i=0;i<M;i++) scanf("%d",&c[i]); printf("Case #%d: ",Case++); for(int i=0;i<M;i++) { printf("%d ",chazhao(c[i],1)); } } return 0; }