HDU 4417 【线段树+离线处理】

http://acm.hdu.edu.cn/showproblem.php?pid=4417

题意：找出给定区间内，有多少个数小于等于给定的数。用线段树维护的话会超时，要用到线段树的离线操作，对询问与数列都进行从小到大的排序，记录下标。从第一个询问开始，遍历数列，满足小于等于就插入到线段树中相应的位置。答案即为当前线段树中有多少个值。转换成了区间和，记录答案，最后一遍输出。

代码如下：

  1 #include<stdio.h>
  2 #include<algorithm>
  3 const int MAXN = 1e5 + 10;
  4 using namespace std;
  5 
  6 int n, m;
  7 int ANS[MAXN];
  8 
  9 struct Node
 10 {
 11     int id, h;
 12 }node[MAXN];
 13 bool cmp1(Node a, Node b)
 14 {
 15     return a.h < b.h;
 16 }
 17 
 18 struct Tree
 19 {
 20     int l, r, num;
 21 }t[MAXN * 4];
 22 
 23 struct Query
 24 {
 25     int l, r, limit, id;
 26 }q[MAXN];
 27 bool cmp2(Query a, Query b)
 28 {
 29     return a.limit < b.limit;
 30 }
 31 
 32 void build(int l, int r, int k)
 33 {
 34     t[k].l = l, t[k].r = r, t[k].num = 0;
 35     if(l == r)
 36         return ;
 37     int mid = (l + r) / 2;
 38     build(l, mid, 2 * k);
 39     build(mid + 1, r, 2 * k + 1);
 40 }
 41 
 42 void up_date(int id, int k)
 43 {
 44     if(t[k].l == t[k].r)
 45     {
 46         t[k].num = 1;
 47         return ;
 48     }
 49     int mid = (t[k].l + t[k].r) / 2;
 50     if(id <= mid)
 51         up_date(id, 2 * k);
 52     else
 53         up_date(id, 2 * k + 1);
 54     t[k].num = t[2 * k].num + t[2 * k + 1].num;
 55 }
 56 
 57 int query(int f_l, int f_r, int k)
 58 {
 59     if(f_l <= t[k].l && f_r >= t[k].r)
 60         return t[k].num;
 61     int mid = (t[k].l + t[k].r) / 2;
 62     if(f_l > mid)
 63         return query(f_l, f_r, 2 * k + 1);
 64     else if(f_r <= mid)
 65         return query(f_l, f_r, 2 * k);
 66     else
 67     {
 68         return query(f_l, mid, 2 * k) + query(mid + 1, f_r, 2 * k + 1);
 69     }
 70 }
 71 
 72 int main()
 73 {
 74     int T, k = 1;
 75     scanf("%d", &T);
 76     while(T --)
 77     {
 78         scanf("%d%d", &n, &m);
 79         build(1, n, 1);
 80         for(int i = 1; i <= n; i ++)
 81         {
 82             scanf("%d", &node[i].h);
 83             node[i].id = i;
 84         }
 85         sort(node + 1, node + 1 + n, cmp1);
 86     //    for(int i = 1; i <= n; i ++)
 87     //        printf("%d
", node[i].h);
 88         printf("Case %d:
", k ++);
 89         for(int i = 1; i <= m; i ++)
 90         {
 91             scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].limit);
 92             q[i].l ++, q[i].r ++;
 93             q[i].id = i;
 94         }
 95         sort(q + 1, q + 1 + m, cmp2);
 96         int j = 1;
 97         for(int i = 1; i <= m; i ++)
 98         {
 99             while(node[j].h <= q[i].limit && j <= n)
100             {
101                 up_date(node[j].id, 1);
102                 j ++;
103             }
104             ANS[q[i].id] = query(q[i].l, q[i].r, 1);
105         }
106         for(int i = 1; i <= m; i ++)
107             printf("%d
", ANS[i]);
108     }
109     return 0;
110 }

View Code