[HDOJ4325]Flowers（树状数组离散化）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4325

关于离散化的简介：http://blog.csdn.net/gokou_ruri/article/details/7723378

假如数据太大，无法作为数组下标来保存对应的属性而采取的一种方法。只需要关注相对大小即可。

我们记下所有的时间数据，再排序。通过二分查找快速定位元素的位置，然后在线段树或者树状数组上仅仅更新这个映射过后的下标位置。因为不需要从线段树或树状数组上直接获取数据（单纯的线段树或树状数组本身是没有意义的，需要搭配相应的数据操作才可以使其称之为线段树或树状数组），也就是说我们更新和查询都是要通过这样一次定位。这样可以解决空间不足的问题。排序后要去重，否则更新到时候可能会更新两次。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 typedef struct Node {
 23     int s;
 24     int t;
 25 }Node;
 26 
 27 const int maxn = 1000010;
 28 int n, m, cnt, tot;
 29 int wt[maxn<<2];
 30 int bit[maxn];
 31 int ask[maxn];
 32 Node f[maxn];
 33 
 34 int lowbit(int x) {
 35     return x & (-x);
 36 }
 37 
 38 void add(int i, int x) {
 39     while(i <= cnt) {
 40         bit[i] += x;
 41         i += lowbit(i);
 42     }
 43 }
 44 
 45 int sum(int i) {
 46     int s = 0;
 47     while(i > 0) {
 48         s += bit[i];
 49         i -= lowbit(i);
 50     }
 51     return s;
 52 }
 53 
 54 int bs(int v) {
 55     int ll = 0, rr = cnt - 1;
 56     int mm;
 57     while(ll <= rr) {
 58         mm = (ll + rr) >> 1;
 59         if(wt[mm] == v) return mm;
 60         if(wt[mm] > v) rr = mm - 1;
 61         if(wt[mm] < v) ll = mm + 1;
 62     }
 63     return -1;
 64 }
 65 
 66 inline bool scan_d(int &num) {
 67     char in;bool IsN=false;
 68     in=getchar();
 69     if(in==EOF) return false;
 70     while(in!='-'&&(in<'0'||in>'9')) in=getchar();
 71     if(in=='-'){ IsN=true;num=0;}
 72     else num=in-'0';
 73     while(in=getchar(),in>='0'&&in<='9'){
 74             num*=10,num+=in-'0';
 75     }
 76     if(IsN) num=-num;
 77     return true;
 78 }
 79 
 80 int main() {
 81     // freopen("in", "r", stdin);
 82     int T, _ = 1;
 83     scan_d(T);
 84     while(T--) {
 85         tot = 0;
 86         memset(bit, 0, sizeof(bit));
 87         scan_d(n); scan_d(m);
 88         for(int i = 1; i <= n; i++) {
 89             scan_d(f[i].s); scan_d(f[i].t);
 90             wt[tot++] = f[i].s; wt[tot++] = f[i].t;
 91         }
 92         for(int i = 1; i <= m; i++) {
 93             scan_d(ask[i]);
 94             wt[tot++] = ask[i];
 95         }
 96         sort(wt, wt+tot);
 97         // int tot = unique(wt,wt+tot) - wt;
 98         cnt = 1;
 99         for(int i = 1; i < tot; i++) {
100             if(wt[i] != wt[i-1]) wt[cnt++] = wt[i];
101         }
102         for(int i = 1; i <= n; i++) {
103             int x = bs(f[i].s) + 1;
104             int y = bs(f[i].t) + 1;
105             add(x, 1);
106             add(y+1, -1);
107         }
108         printf("Case #%d:
", _++);
109         for(int i = 1; i <= m; i++) {
110             int ans = bs(ask[i]) + 1;
111             printf("%d
", sum(ans));
112         }
113     }
114     return 0;
115 }

[HDOJ4325]Flowers（树状数组 离散化）

[HDOJ4325]Flowers（树状数组离散化）