首页 > 代码库 > （树状数组+离线查询）HDU 4417 - Super Mario
（树状数组+离线查询）HDU 4417 - Super Mario
题意：
给定一个数列，最多10万次查询l到r不超过h的数字的个数。
分析：
唉，太菜啦。
在线做法应该比较明显，区间维护平衡树，用线段树套平衡树，或者分块套平衡树，应该都能A，但是没试过，只是BB，如有错误欢迎指正。
其实最方便的做法离线做法，太巧妙啦。
把数列按升序排列，把所有查询按h升序排列。
每次查询把比h的小的位置标记为1，查询用bit的sum(r)-sum(l-1)即可
因为都是单调的，所以很方便。
其实很多没有修改的区间问题都可以转化成离线问题。
甚至于一些带修改的题都可以离线。
这些题关键在于如何转化，也关键在于做题者的脑洞。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <vector> 6 7 8 using namespace std; 9 10 const int inf = 0x3f3f3f3f;11 const int maxn = 100010;12 13 int bit[maxn];14 int t, n, q;15 16 int sum(int i) {17 int s = 0;18 while(i > 0) {19 s += bit[i];20 i -= i & -i;21 }22 return s;23 }24 25 void add(int i, int x) {26 while(i <= n) {27 bit[i] += x;28 i += i & -i;29 }30 }31 32 struct Q {33 int l, r, h;34 int index;35 } query[maxn];36 37 bool cmp(Q a, Q b) {38 return a.h < b.h;39 }40 41 pair<int, int> a[maxn];42 int ans[maxn];43 44 int main() {45 scanf("%d", &t);46 int kase = 0;47 while(t--) {48 memset(bit, 0, sizeof(bit));49 scanf("%d%d", &n, &q);50 for(int i = 1; i <= n; i++) {51 scanf("%d", &a[i].first);52 a[i].second = i;53 }54 for(int i = 0; i < q; i++) {55 scanf("%d%d%d", &query[i].l, &query[i].r, &query[i].h);56 query[i].l++, query[i].r++;57 query[i].index = i;58 }59 sort(query, query + q, cmp);60 sort(a + 1, a + n + 1);61 int left = 1;62 for(int i = 0; i < q; i++) {63 while(left <= n && a[left].first <= query[i].h) {64 add(a[left].second, 1);65 left++;66 }67 int r = sum(query[i].r);68 int l = sum(query[i].l - 1);69 ans[query[i].index] = r - l;70 }71 printf("Case %d:\n", ++kase);72 for(int i = 0; i < q; i++) {73 printf("%d\n", ans[i]);74 }75 }76 77 78 79 return 0;80 81 }
（树状数组+离线查询）HDU 4417 - Super Mario
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。