[原创]HDU 4417 Super Mario [树状数组+离线操作]【数据结构】

2017-01-18 16:28:55 Tabris_ 阅读数：239

博客爬取于2020-06-14 22:42:05
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54602437

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4417
------------------------------------------------------------------------------.
Super Mario

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6059 Accepted Submission(s): 2635

Problem Description
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.

Input
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.)

Output
For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.

Sample Input
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

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

Source
2012 ACM/ICPC Asia Regional Hangzhou Online
------------------------------------------------------------------------------.
题目大意：
就是给你长度为N个序列，每个序列由一个高度为 $h_i$ 的木棍,现在有M个询问,问你在[L,R]区间内小于等于H的木棍有多少,即 $|A| ,A=\{a_i | a_i<=h,L<=i<=R\}$ 。

解题思路：

如果题目中没有要求 $<=h$ ,那么可以直接求[L,R]区间内的数就行了，

很明显，直接在线的话并不能在良好复杂度内解决问题（后来发现是有的只不过我不会。。），离线的话考虑还是很容易的。

首先题目既然要求比h小的，那么我们可以对 $h_i$ 从小到大排序,每次都将比查询的h小的放入数据结构中,然后在[L,R]查询到的一定满足 $h_i<h$ .这个时候我们同样将查询操作，按照h操作从大到小排序，每次查询的时候我们都将满足 $h_i<h$ 的放入数据结构中，这样的话不算查询的复杂度一共是 $O(N+M)$ ,通过数据结构的优化，查询操作的复杂度就是 $O(log_2N)$ 的。综复杂度就是 $O(N+M*log_2N)$ ,

这种查询区间的操作用[树状数组/线段树]都能很好完成,树状数组的话实现相对容易,所以我采用了树状数组.
因为每次查询的时候,计算的数都是 $<h$ 的,所以我们不用考虑他的大小,只要在其对应的位置下**+1**就行了,这样每次查询的时候就是查询其查询区间内有几个1即可, $getSum(r)-getSum(l-1);$ 最后用一个数组来记录结果就行了.

最后的最后!!!
“Case X:”!!!
它的这里居然没有***“#”***号,我cacacaca,找了800年的bug…

附本题代码
------------------------------------------------------------------------------.

# include <bits/stdc++.h>
using namespace std;
const int    N   = 100000+7;
/***********************************************************************/
struct node1{
    int a,id;
}aa[N];
struct node2{
    int l,r,h,id;
}bb[N];
bool cmp1(node1 A,node1 B){
    return A.a<B.a;
}
bool cmp2(node2 A,node2 B){
    return A.h<B.h;
}

# define lowbit(x) (x&-x)
int tree[N];
void update(int ind,int val){
    for(int i=ind;i<=N;i+=lowbit(i))
        tree[i]+=val;
}
int getSum(int ind){
    int ans = 0;
    for(int i=ind;i;i-=lowbit(i)) ans+=tree[i];
    return ans;
}

int ans[N];
int main(){
    int _,kcase=0;
    scanf("%d",&_);
    while(_--){
        memset(tree,0,sizeof(tree));

        int n,m;
        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++){
            scanf("%d",&aa[i].a);
            aa[i].id=i;
        }

        int l,r,h;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&l,&r,&h);
            bb[i].l=l+1,bb[i].r=r+1,bb[i].h=h,bb[i].id=i;
        }

        sort(aa+1,aa+n+1,cmp1);
        sort(bb+1,bb+m+1,cmp2);

        for(int i=1,j=1;i<=m;i++){
            while(j<=n&&bb[i].h>=aa[j].a) update(aa[j++].id,1);
            ans[bb[i].id]=getSum(bb[i].r)-getSum(bb[i].l-1);
        }

        printf("Case %d:\n",++kcase);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}