首页 > 其他 > 详细

HDU 4417

时间:2018-08-02 22:37:54      阅读:215      评论:0      收藏:0      [点我收藏+]

题意略。

思路:

仔细思考这个题目会发现,它其实是要你查询两次,第一是要规定l,r的范围,第二是要在范围内查询小于等于H的个数。所以有的人说要用主席树。

现在,如果我们能省去范围内对h的查询呢?也就是说,在查询范围时,我们就要保证这个范围内的所有hi都小于等于H的数字。

我们可以离线地来做。这样就只需要树状数组了,不再需要主席树了。

详见代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

struct node{
    int idx,numb;
    node(int idx = 0,int numb = 0){
        this->idx = idx;
        this->numb = numb;
    }
};
struct query{
    int l,r,h,id;
    query(int l = 0,int r = 0,int h = 0,int id = 0){
        this->l = l,this->r = r,this->h = h;
        this->id = id;
    }
};

node store[maxn];
query depot[maxn];
int BIT[maxn],n,m,ans[maxn];

bool cmp1(const node& n1,const node& n2){
    return n1.numb < n2.numb;
}
bool cmp2(const query& q1,const query& q2){
    return q1.h < q2.h;
}
int lowbit(int k){
    return (k & -k);
}
void add(int pos,int val){
    while(pos <= n){
        BIT[pos] += val;
        pos += lowbit(pos);
    }
}
int sum(int pos){
    int ret = 0;
    while(pos > 0){
        ret += BIT[pos];
        pos -= lowbit(pos);
    }
    return ret;
}

int main(){
    int T,cas = 1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        memset(BIT,0,sizeof(BIT));
        for(int i = 1;i <= n;++i){
            scanf("%d",&store[i].numb);
            store[i].idx = i;
        }
        sort(store + 1,store + 1 + n,cmp1);
        for(int i = 0;i < m;++i){
            scanf("%d%d%d",&depot[i].l,&depot[i].r,&depot[i].h);
            depot[i].id = i;
            depot[i].l += 1;
            depot[i].r += 1;
        }
        sort(depot,depot + m,cmp2);
        int last = 1;
        for(int i = 0;i < m;++i){
            int h = depot[i].h,l = depot[i].l;
            int r = depot[i].r,id = depot[i].id;
            for(;last <= n && store[last].numb <= h;++last)
                add(store[last].idx,1);
            int t = sum(r) - sum(l - 1);
            ans[id] = t;
        }
        printf("Case %d:\n",cas++);
        for(int i = 0;i < m;++i)
            printf("%d\n",ans[i]);
    }
    return 0;
}

 

HDU 4417

原文:https://www.cnblogs.com/tiberius/p/9409784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!