首页 > ACM题库 > HDU-杭电 > HDU 4417-Super Mario-树状数组-[解题报告]HOJ
2015
07-16

HDU 4417-Super Mario-树状数组-[解题报告]HOJ

Super Mario

问题描述 :

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

输入:

The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

输出:

The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

样例输入:

1
10 10
0 5 2 7 5 4 3 8 7 7 
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

样例输出:

Case 1:
4
0
0
3
1
2
0
1
5
1

来源:http://acm.hdu.edu.cn/showproblem.php?pid=4417

题意:给一些数,数中有重复的。还有一些询问,问的是[L,R] 区间内有多少个数小于h,有多次询问。

思路:普通方法的话肯定会超时,题目问[L,R]区间内小于h的数有多少个,则可以算出cal(R) 和 cal(L – 1), 两者相减就是答案。这类问题和求逆序数的问题非常类似,即求一个数前面有几个数比它小。求逆序数的问题可以用树状数组解决。

但是用树状数组解决问题需要一个条件就是给的数是从1到n,显然这道题目是不满足这个条件的。但是我们可以转化过去。最近做了一些树状数组的题目,发现很多问题都是需要转化一下。如何转化到树状数组上才是问题的难点。

一些问题好像是不满足树状数组,因为题目中限制 了一些其它的条件,这时我们可以根据题目问题的特点,排除影响树状数组的因素,从而使用树状数组。

比如stars这道题目,因为题目限制 了两个条件,所以不能直接用树状数组,但是当我们把一个因素排序后,另一个因素就满足了树状数组的条件,而我们仔细考虑的话,发现对一个因素排序是不影响最后结果的。对这道题目来说,因为所给的数有重复的,且问的数也不一定出现在给的数中,但是我们可以对给的数和问的数排序,在固定一些因素后,就可以使用树状数组了,而且这最后是不影响最后结果的。

代码:

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 100010;
struct dit{
	int num,id;
}dd[N];
struct ask{
	int lp,rp,value,id;
}aa[N];
int cnt[N];
bool cmp1(dit a,dit b){
	return a.num < b.num;
}
bool cmp2(ask a,ask b){
	return a.value < b.value;
}
int inline lowbit(int x){
	return x & (-x);
}
void inline update(int x){
	while(x < N){
	   cnt[x]++;
	   x += lowbit(x);
	}
}
int inline sum(int x){
	int s = 0;
	while(x > 0){
	  s += cnt[x];
	  x -= lowbit(x);
	}
	return s;
}
int main(){
	//freopen("1.txt","r",stdin);
	int numcase;
	scanf("%d",&numcase);
	for(int ca = 1; ca <= numcase; ++ca){
	   int n,m;
	   memset(cnt,0,sizeof(cnt));
	   scanf("%d%d",&n,&m);
	   for(int i = 0; i < n; ++i){
	      scanf("%d",&dd[i].num);
		  dd[i].id = i + 1;
	   }
	   int x,y;
	   for(int i = 0; i < m; ++i){
	      scanf("%d%d%d",&x,&y,&aa[i].value);
		  aa[i].lp = x + 1;
		  aa[i].rp = y + 1;
		  aa[i].id = i + 1;
	   }
	   sort(dd,dd+n,cmp1);
	   sort(aa,aa+m,cmp2);
	   int ans[N] = {0};
	   for(int aski = 0,ditj = 0; aski < m; ++aski){
		   while(ditj < n && aa[aski].value >= dd[ditj].num){
		      update(dd[ditj].id);
			  ditj++;
		   }
		   ans[aa[aski].id] = sum(aa[aski].rp) - sum(aa[aski].lp - 1);
	   }
	   printf("Case %d:\n",ca);
	   for(int i = 1; i <= m; ++i){
	      printf("%d\n",ans[i]);
	   }
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wmn_wmn/article/details/8034181