本文主要是介绍HDU - 4417 Super Mario，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题面
传送门
2.解题思路
题意要求是给定一组数，每次询问给出一对[l,r]和一个h，要求回答[l,r]之间有几个数比h小。
这道题目没有想出来，网上搜索到有使用高级数据结构划分树，弱菜不会使用划分树，只好按照别人的思路写了一个树状数组版的。离线的解题方法是容易想到的，还有就是不能直接使用树状数组，要先转化一下。转化只需要使用一句话
我们不回答[l,r]之间有几个数比h小，我们只需要回答比h小的数中有几个是介于[l,r]之间的。
具体的看代码。
3.解题代码
/*****************************************************************> File Name: tmp.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年02月19日 星期五 16时47分54秒****************************************************************/
# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;const int size = 100000 + 10;
typedef long long ll;int BIT[size];
int lowbit(int x){return x-(x&(x-1));
}
void Add(int pos,int v){while (pos<size){BIT[pos] += v;pos += lowbit(pos);//if (debug) cout << "pos = " << pos << '\n';}
}
int Sum(int pos){int ret = 0;while (pos>0){ret += BIT[pos];pos -= lowbit(pos);}return ret;
}struct data{int num,id;bool operator < (const data& cmper)const{return num < cmper.num;}
}in[size];struct query{int l,r,h,id;bool operator < (const query& cmper)const{return h < cmper.h;}
}q[size];int ans[size];
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);int i,j,k;int T,ncase=0;cin >> T;while (T--){memset(BIT,0,sizeof(BIT));cout << "Case " << (++ncase) << ":" << '\n';int n,m;cin >> n >> m;for (i=0;i<n;i++){cin >> in[i].num;in[i].id = i+1;}for (i=0;i<m;i++){cin >> q[i].l >> q[i].r >> q[i].h;q[i].l++;q[i].r++;q[i].id = i;}sort(in,in+n);sort(q,q+m);for (j=i=0;i<m;i++){while (j<n&&in[j].num<=q[i].h){Add(in[j].id,1);j++;}ans[q[i].id] = Sum(q[i].r) - Sum(q[i].l-1);}for (i=0;i<m;i++){cout << ans[i] << '\n';}}return 0;
}
这篇关于HDU - 4417 Super Mario的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
