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 }