HDU 4417 - Super Mario

  1 /*
  2 ID:esxgx1
  3 LANG:C++
  4 PROG:hdu4417
  5 */
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <algorithm>
 10 using namespace std;
 11 
 12 #define MAXN    100007
 13 
 14 int v[MAXN * 4];
 15 
 16 #define recursive_def    int l, int r, int i
 17 #define lsi        i<<1
 18 #define rsi        i<<1 | 1
 19 #define lsn        l, m, lsi
 20 #define rsn        m+1, r, rsi
 21 #define pushup    v[i] = v[lsi] + v[rsi];
 22 
 23 void build(recursive_def)
 24 {
 25     v[i] = 0;
 26     if (l == r) return;
 27     else {
 28         int m = (l+r) >> 1;
 29         build(lsn);
 30         build(rsn);
 31     }
 32 }
 33 
 34 void update(int x, recursive_def)
 35 {
 36     if (l == r) v[i] += 1;
 37     else {
 38         int m = (l+r) >> 1;
 39         if (x <= m) update(x, lsn);
 40         else update(x, rsn);
 41         pushup
 42     }
 43 }
 44 
 45 int query(int L, int R, recursive_def)
 46 {
 47     if (L <= l && r <= R) return v[i];
 48     int m = (l+r) >> 1;
 49     int rslt;
 50     if (L <= m) rslt = query(L, R, lsn);
 51     else rslt = 0;
 52 
 53     if (m < R) rslt += query(L, R, rsn);
 54     return rslt;
 55 }
 56 
 57 struct A{
 58     int x, h;
 59 } brick[MAXN];
 60 
 61 int cmp1(const A &a, const A &b)
 62 {
 63     return a.h < b.h;
 64 }
 65 
 66 #define MAXM    100007
 67 
 68 struct B{
 69     int L, R, H, d, cnt;
 70 } qs[MAXM];
 71 
 72 int cmp2(const B &a, const B &b)
 73 {
 74     return a.H < b.H;
 75 }
 76 
 77 int cmp3(const B &a, const B &b)
 78 {
 79     return a.d < b.d;
 80 }
 81 
 82 int main(void)
 83 {
 84     #ifndef ONLINE_JUDGE
 85     freopen("in.txt", "r", stdin);
 86     #endif
 87     int T;
 88     scanf("%d", &T);
 89     for(int t=1; t<=T; ++t) {
 90         int N, M;
 91         printf("Case %d:\n", t);
 92         scanf("%d%d", &N, &M);
 93         for(int i=0; i<N; ++i) {
 94             scanf("%d", &brick[i].h);
 95             brick[i].x = i;
 96         }
 97         sort(brick, brick + N, cmp1);
 98         for(int i=0; i<M; ++i) {
 99             scanf("%d%d%d", &qs[i].L, &qs[i].R, &qs[i].H);
100             qs[i].d = i;
101         }
102         sort(qs, qs+M, cmp2);
103         build(0, N-1, 1);
104         int bb = 0;
105         for(int i=0; i<M; ++i) {
106             while(brick[bb].h <= qs[i].H) {
107                 update(brick[bb].x, 0, N-1, 1);
108                 if (++bb >= N) break;
109             }
110             qs[i].cnt = query(qs[i].L, qs[i].R, 0, N-1, 1);
111         }
112         sort(qs, qs+M, cmp3);
113         for(int i=0; i<M; ++i)
114             printf("%d\n", qs[i].cnt);
115     }
116     return 0;
117 }