先来一个离线版本的线段树：

1 /*  2 ID:esxgx1  3 LANG:C++  4 PROG:hdu4417  5 */  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          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) 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
         
        
       
      
     

 

2014-07-25 19:50:07

Accepted

265MS

3100K

1980 B

G++