HDU 4417 树状数组

50 阅读 0 评论 33 点赞

我是靠谱客的博主细腻水蜜桃，最近开发中收集的这篇文章主要介绍HDU 4417 树状数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

</pre><pre name="code" class="cpp">/*
    HDU 4417 Super Mario
    题意：给定一个数组，若干询问，每次询问区间不大于K的数的个数


    将询问按K排序，保证每次处理当前K的时候，数组中不大于K的数已经被加到树状数组中
    然后求前缀和即可
*/
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
using namespace std;


const int size=111111;
typedef long long ll;
typedef double dd;


int t,n,m,l,r,h,a[size],ans[size];
vector<int> V,Q[size],P[size];


int b[size];
void add(int k){
    for(;k<=n;k+=k&-k)b[k]++;
}
int get(int k){
    int ans=0;
    for(;k>0;k-=k&-k)ans+=b[k];
    return ans;
}


int main(){
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++){
        scanf("%d%d",&n,&m);
        V.clear();
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            V.push_back(a[i]);
            b[i]=0;
            P[i].clear();
            Q[i].clear();
        }
        sort(V.begin(),V.end());
        V.erase(unique(V.begin(),V.end()),V.end());
        for(int i=1;i<=n;i++){
            a[i]=upper_bound(V.begin(),V.end(),a[i])-V.begin();
            Q[a[i]].push_back(i);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&l,&r,&h);
            h=upper_bound(V.begin(),V.end(),h)-V.begin();
            P[h].push_back(i);
            P[h].push_back(l);
            P[h].push_back(r);
        }
        for(int i=0;i<=V.size();i++){
            for(int j=0;j<Q[i].size();j++)add(Q[i][j]);
            for(int j=0;j<P[i].size();j+=3)ans[P[i][j]]=get(P[i][j+2]+1)-get(P[i][j+1]);
        }
        printf("Case %d:n",ca);
        for(int i=0;i<m;i++)printf("%dn",ans[i]);
    }
}