HDU 4417 Super Mario（线段树||树状数组+离线操作之树状数组篇）

朴灿烈づ我的快乐病毒、 2022-06-11 09:52 135阅读 0赞

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

题解：

之前写了这篇的线段树版，附上链接：[点击打开链接][Link 1]，刚刚完成了这题的树状数组版，如果要看思路去线段树篇看

然后写完了树状数组的写法发现树状数组真的很快！！！比线段树快了一倍多，然后用的内存也小了很多！！不过要注意一些细节处理，不然会错

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    using namespace std;
    int sum[100005];//存树状数组的求和数组
    int n;
    int lowbit(int x)
    {
        return x&(-x);
    }
    void update(int pos)//日常更新
    {
        while(pos<=n+1)//请注意这里的细节处理，之后会说
        {
            sum[pos]++;
            pos+=lowbit(pos);
        }
    }
    int query(int pos)//日常询问
    {
        int ans=0;
        while(pos>0)
        {
            ans+=sum[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
    struct qu
    {
        int id;
        int h;
        int l,r;
    }q[100005];//存询问
    struct sub
    {
        int pos;
        int h;
    }s[100005];//存序列
    int cmp1(qu x,qu y)
    {
        return x.h<y.h;
    }
    int cmp2(sub x,sub y)
    {
        return x.h<y.h;
    }
    int answer[100005];//存答案
    int main()
    {
        int i,j,k,m,test,o,tot;
        scanf("%d",&test);
        for(o=1;o<=test;o++)
        {
            memset(sum,0,sizeof(sum));
            scanf("%d%d",&n,&m);
            for(i=0;i<n;i++)
            {
                scanf("%d",&s[i].h);
                s[i].pos=i;
                s[i].pos+=2;//细节处理，由于我们询问的时候是用x-lowbit(x)减到0为止，但是这题的区间是从0开始的，我们无法得到0处的值，+2是因为后面区间求和要-1
            }//所以总体加上了2，对结果不影响，但是不加就会有问题，当x等于0的时候无限循环和剪出来数组下标为负之类的麻烦
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].h);
                q[i].r+=2;
                q[i].l+=2;//整体+2
                q[i].id=i;
            }
            sort(s,s+n,cmp2);
            sort(q,q+m,cmp1);//排序
            tot=0;
            for(i=0;i<m;i++)
            {
                while(tot<n&&q[i].h>=s[tot].h)
                {
                    update(s[tot].pos);//单点更新
                    tot++;
                }
                answer[q[i].id]=query(q[i].r)-query(q[i].l-1);//这里实现了树状数组的区间求和
            }
            printf("Case %d:\n",o);
            for(i=0;i<m;i++)
                printf("%d\n",answer[i]);
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/qq_37497322/article/details/76684720