hdu 4417 Super Mario(树状数组+离线处理)

按H排序，每次查询把不大于H的值插入到树状数组中的相应位置并完成查询。
171MS
View Code
  1 /*
  2 Author:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <iostream>
  8 #include <cmath>
  9 #include <cstring>
 10 #include <algorithm>
 11 #include <string>
 12 #include <utility>
 13 #include <vector>
 14 #include <queue>
 15 #include <stack>
 16 #include <map>
 17 #include <set>
 18 using namespace std;
 19 typedef long long ll;
 20 #define pii pair<int,int>
 21 #define pb push_back
 22 #define mp make_pair
 23 #define fi first
 24 #define se second
 25 #define lowbit(x) (x&(-x))
 26 const int INF = 2147483647;
 27 
 28 const int maxn = 100005;
 29 int C[maxn];
 30 struct query
 31 {
 32     int l,r,h,pos,ans;
 33 }q[maxn];
 34 struct bri
 35 {
 36     int num,pos;
 37 }a[maxn];
 38 int n,m;
 39 
 40 int cmp1(bri a,bri b)
 41 {
 42     return a.num<b.num;
 43 }
 44 int cmp2(query a,query b)
 45 {
 46     return a.h<b.h;
 47 }
 48 int cmp3(query a,query b)
 49 {
 50     return a.pos<b.pos;
 51 }
 52 void add(int x,int pos)
 53 {
 54     while(pos<=n)
 55     {
 56         C[pos] += x;
 57         pos += lowbit(pos);
 58     }
 59 }
 60 int sum(int pos)
 61 {
 62     int res = 0;
 63     while(pos > 0)
 64     {
 65         res += C[pos];
 66         pos -= lowbit(pos);
 67     }
 68     return res;
 69 }
 70 int main()
 71 {
 72     #ifndef ONLINE_JUDGE
 73     freopen("in","r",stdin);
 74     #endif
 75     int T;
 76     int cas=0;
 77     scanf("%d",&T);
 78     while(T--)
 79     {
 80         scanf("%d%d",&n,&m);
 81         memset(C,0,(n+1)*sizeof(int));
 82         for(int i=0;i<n;i++)
 83         {
 84             scanf("%d",&a[i].num);
 85             a[i].pos = i + 1;
 86         }
 87         sort(a,a+n,cmp1);
 88         printf("Case %d:\n",++cas);
 89         for(int i=0;i<m;i++)
 90         {
 91             scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
 92             q[i].pos=i + 1;
 93         }
 94         sort(q,q+m,cmp2);
 95         int k=0;
 96         for(int i=0;i<m;i++)
 97         {
 98             while(a[k].num <= q[i].h && k < n)
 99             {
100                 add(1,a[k].pos);
101                 k++;
102             }
103             q[i].ans = sum(q[i].r+1) - sum(q[i].l);
104         }
105         sort(q,q+m,cmp3);
106         for(int i=0;i<m;i++)
107         {
108             printf("%d\n",q[i].ans);
109         }
110     }
111     return 0;
112 }
by Farmer