HDU 4417 Super Mario （树状数组）

48 阅读 0 评论 32 点赞

我是靠谱客的博主清爽老师，最近开发中收集的这篇文章主要介绍HDU 4417 Super Mario （树状数组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：

首先我们先回顾一下树状数组。树状数组的的直接目的即区间求和（logn）。但由于具有logn单点修改的功能使得区间求和更为方便。
对于这道题来说，我们先对m个询问中的h升序排序，利用了<=h1的元素一定也<=h2这个递推式，然后将n个数也排序，但同时需要记录这些数原本的位置信息。
对于每个询问，我们将符合hi条件的点加入树状数组，注意，我们是将这个点原来的位置加入树状数组（数量是1）。这样构造出来的数组即是满足当前所有点<=hi的情况下，getsum_tree[i]得到的即是小于等于位置i的满足条件的点的个数。
对于某个区间i，j来说，getsum_tree[j] - getsum_tree[i]。注意根据实际情况讨论边界。

代码：

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

int n,m;
int c[100010];

struct san{
    int val,p;
    san(){}
    san(int vv,int i){val = vv,p = i;}
}lisan[100010];

struct node1{
    int l,r,h,num;
    node1(){}
    node1(int ll,int rr,int hh,int numm){
        l = ll,r = rr, h = hh, num = numm;
    }
}query[100010];

void insert(int i,int x){
    while(i <= n){
        c[i] += x;
        i += (i&-i);
    }
}
int getsum(int i){
    int sum = 0;
    while(i > 0){
        sum += c[i];
        i -= (i&-i);
    }
    return sum;
}

int ans[100010];

bool cmp(const san&a, const san&b){return a.val<b.val;}
bool cmp2(const node1&a, const node1&b){return a.h<b.h;}

int main(){
    int t;
    cin>>t;
    int nca = 0;
    while(t--){
        memset(c,0,sizeof(c));
        memset(lisan,0,sizeof(lisan));
        nca++;
        scanf("%d%d",&n,&m);
        int temp;
        for(int i = 1;i <= n;i++){
            scanf("%d",&temp);
            lisan[i] = san(temp,i);
        }
        for(int i = 1;i <= m;i++){
            scanf("%d%d%d",&query[i].l,&query[i].r,&query[i].h);
            query[i].num = i;
        }
        sort(lisan+1,lisan+1+n,cmp);
        sort(query+1,query+1+m,cmp2);

        int now = 1;
        for(int i = 1;i <= n;i++){
            if(lisan[i].val <= query[now].h){
                insert(lisan[i].p,1);
            }
            else if(now <= m-1){
                ans[query[now].num] = getsum(query[now].r+1) - getsum(query[now].l) ;
                now++;
                i--;
            }
            else break;
        }
        for(int i = now;i <= m;i++){
            ans[query[i].num] = getsum(query[i].r+1) - getsum(query[i].l);
        }
        printf("Case %d:n",nca);
        for(int i = 1;i <= m;i++){
            printf("%dn",ans[i]);
        }
    }
    return 0;
}