hdu 4325 Flowers

题目大意：一个农园有n个花朵，给出每朵花的开花时间（用区间表示），求在特定时间点的开花的花朵数量。
思路：离散化，线段树。在建树时有些点表示单个时间点，有些要表示时间区间。然后单点查询即可。
View Code
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 #define lson l,m,rt<<1
  6 #define rson m+1,r,rt<<1|1
  7 #define maxn 100010
  8 struct node
  9 {
 10     int cnt;
 11 }setree[maxn<<3];
 12 int xx[maxn<<2];
 13 struct 
 14 {
 15     int l,r;
 16 }info[maxn<<3];
 17 int left[maxn];
 18 int right[maxn];
 19 void build(int l,int r,int rt)
 20 {
 21     setree[rt].cnt=0;
 22     if(l==r)
 23     return;
 24     int m=(l+r)>>1;
 25     build(lson);
 26     build(rson);
 27 }
 28 void pushdown(int rt)
 29 {
 30     if(setree[rt].cnt){
 31         setree[rt<<1].cnt+=setree[rt].cnt;
 32         setree[rt<<1|1].cnt+=setree[rt].cnt;
 33         setree[rt].cnt=0;
 34     }
 35 }
 36 void update(int l,int r,int rt,int L,int R)
 37 {
 38     if(L<=l&&r<=R){
 39         setree[rt].cnt++;
 40         return;
 41     }
 42     pushdown(rt);
 43     int m=(l+r)>>1;
 44     if(L<=m)
 45     update(lson,L,R);
 46     if(R>m)
 47     update(rson,L,R);
 48 }
 49 int query(int l,int r,int rt,int num)
 50 {
 51     if(l==r)
 52     return setree[rt].cnt;
 53     pushdown(rt);
 54     int m=(l+r)>>1;
 55     if(num<=m)
 56     return query(lson,num);
 57     else 
 58     return query(rson,num);
 59 }
 60 int binsearch(int l,int r,int key)
 61 {
 62     if(l>r)
 63     return -1;
 64     int m=(l+r)>>1;
 65     if(info[m].l<=key&&key<=info[m].r)
 66     return m;
 67     if(info[m].l>key)
 68     return binsearch(l,m-1,key);
 69     else if(info[m].r<key)
 70     return binsearch(m+1,r,key);
 71 }
 72 int main()
 73 {
 74     int n,k,t,m,i,cas=1;
 75     scanf("%d",&t);
 76     while(t--){
 77         scanf("%d%d",&n,&m);
 78         k=1;
 79         for(i=1;i<=n;i++){
 80             scanf("%d%d",left+i,right+i);
 81             xx[k++]=left[i];
 82             xx[k++]=right[i];
 83         }
 84         sort(xx+1,xx+k);
 85         int nk=2;
 86         for(i=2;i<k;i++)
 87         if(xx[i]!=xx[i-1])
 88         xx[nk++]=xx[i];
 89         k=nk;
 90         int k1=2;
 91         info[1].l=info[1].r=xx[1];
 92         for(i=2;i<k;i++){
 93             if(xx[i]-xx[i-1]>1){
 94                 info[k1].l=xx[i-1]+1;
 95                 info[k1].r=xx[i]-1;
 96                 k1++;
 97             }
 98             info[k1].l=xx[i];
 99             info[k1].r=xx[i];
100             k1++;
101         }
102         k=k1;
103         build(1,k-1,1);
104         for(i=1;i<=n;i++){
105             int l=binsearch(1,k-1,left[i]);
106             int r=binsearch(1,k-1,right[i]);
107             update(1,k-1,1,l,r);
108         }
109         printf("Case #%d:\n",cas++);
110         while(m--){
111             int a;
112             scanf("%d",&a);
113             a=binsearch(1,k-1,a);
114             if(a==-1)
115             printf("0\n");
116             else
117             printf("%d\n",query(1,k-1,1,a));
118         }
119     }
120     return 0;
121 }