【HDOJ】4325 Flowers

树状数组+离散化的题目，一直在思考为什么结果不一样，后来才发现花开了就是开了不会再谢了。

 /* 4325 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 #define MAXN 100005

 typedef struct {

     int s, t;

 } node_t;

 node_t nodes[MAXN];

 int qi[MAXN];

 int buf[MAXN*];

 int sum[MAXN];

 inline int lowbit(int x) {

     return -x&x;

 }

 void update(int i, int v, int n) {

     while (i <= n) {

         sum[i] += v;

         i += lowbit(i);

     }

 }

 int query(int i) {

     int ret = ;

     while (i) {

         ret += sum[i];

         i -= lowbit(i);

     }

     return ret;

 }

 int main() {

     int t, n, m, l;

     int i, j, k, tmp;

     int a, b, c;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

     #endif

     scanf("%d", &t);

     for (int tt=; tt<=t; ++tt) {

         scanf("%d %d", &n, &m);

         l = ;

         for (i=; i<n; ++i) {

             scanf("%d %d", &nodes[i].s, &nodes[i].t);

             buf[l++] = nodes[i].s;

             buf[l++] = nodes[i].t;

         }

         for (i=; i<m; ++i) {

             scanf("%d", &qi[i]);

             buf[l++] = qi[i];

         }

         // discretization

         buf[l++] = ;

         sort(buf, buf+l);

         c = unique(buf, buf+l) - buf;

         memset(sum, , sizeof(sum));

         for (i=; i<n; ++i) {

             a = lower_bound(buf, buf+c, nodes[i].s) - buf + ;

             b = lower_bound(buf, buf+c, nodes[i].t) - buf + ;

             update(a, , c);

             update(b+, -, c);

         }

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

         for (i=; i<m; ++i) {

             j = lower_bound(buf, buf+c, qi[i]) - buf + ;

             k = query(j);

             printf("%d\n", k);

         }

     }

     return ;

 }