首页 > 代码库 > [HDU 4417] Super Mario (树状数组)

[HDU 4417] Super Mario (树状数组)

2024-07-31 22:43:15   219人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4417

题目大意：给你n个数，下标为0到n-1，m个查询，问查询区间[l,r]之间小于等于x的数有多少个。

 

写的时候逗比了。。。还是写的太少了。。

我们按照x从小到大排序来查询，然后找区间上的点，如果小于等于它就插入，然后看这个区间内插入了多少个点。

点也是可以排序的。。

详见代码：

 1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 typedef pair<int,int> PII; 8  9 const int MAX_N = 100100;10 int bit[MAX_N];11 PII a[MAX_N];12 int ans[MAX_N];13 struct Node{14     int ql,qr,qh,idx;15     bool operator<(const Node& a) const{16         return qh<a.qh;17     }18 };19 Node qq[MAX_N];20 int T,n,m;21 int ub;22 23 void add(int i,int x){24     while( i<=n ){25         bit[i] += x;26         i+=i&-i;27     }28 }29 30 int sum(int i){31     int res = 0;32     while( i>0 ){33         res += bit[i];34         i -= i&-i;35     }36     return res;37 }38 39 40 int main(){41     scanf("%d",&T);42     int kase = 1;43     while( T-- ){44         memset(bit,0,sizeof(bit));45         printf("Case %d:\n",kase++);46         scanf("%d%d",&n,&m);47         int ptr = 0;48         for(int i=0;i<n;i++){49             scanf("%d",&a[i].first);50             a[i].second = i+1;51         }52         for(int i=0;i<m;i++){53             scanf("%d%d%d",&qq[i].ql,&qq[i].qr,&qq[i].qh);54             qq[i].idx = i;55         }56 57         sort(qq,qq+m);58         sort(a,a+n);59 60         int j=0;61         for(int i=0;i<m;i++){62             while(j<n && a[j].first<=qq[i].qh ){63                 add(a[j].second,1);64                 j++;65             }66             ans[qq[i].idx] = sum( qq[i].qr+1 ) - sum(qq[i].ql);67         }68 69         for(int i=0;i<m;i++){70             printf("%d\n",ans[i]);71         }72 73     }74     return 0;75 }

 

[HDU 4417] Super Mario (树状数组)


联系
我们