频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 4417 2012杭州网络赛
2012-09-25 10:06:27           
收藏   我要投稿

给出 n 个数,m个询问,对于 每个询问 输出[l,r]区间里面 大于 h 的数个数,由于n和m都很大,直接搞肯定不行,可以用线段树求解。
线段树 每个区间 保存 与该区间长度一样 对应 的 数据段,然后进行排序,查询的时候 如果该区间包含在 要询问的区间,那么直接二分查上界即可,否则继续向下询问。。
[cpp]
#include<iostream> 
#include<algorithm> 
using namespace std; 
 
#define lson u<<1 
#define rson u<<1|1 
#define MAXN 100010 
 
int dat[MAXN]; 
 
struct Node{ 
    int lef,rig; 
    //int sum; 
    int *sub; 
 
}T[MAXN<<2]; 
 
void Build(int u,int l,int r){ 
    T[u].lef=l; 
    T[u].rig=r; 
    T[u].sub=new int[r-l+3]; 
    int subc=0; 
    for(int i=l;i<=r;i++)T[u].sub[subc++]=dat[i]; 
    sort(T[u].sub,T[u].sub+subc); 
    if(l==r)return; 
    int mid=(l+r)>>1; 
    Build(lson,l,mid); 
    Build(rson,mid+1,r); 

 
void finalizer(int u,int l,int r){ 
    delete[] T[u].sub; 
    if(l==r)return; 
    int mid=(l+r)>>1; 
    finalizer(lson,l,mid); 
    finalizer(rson,mid+1,r); 

 
int Query(int u,int l,int r,int h){ 
    if(l<=T[u].lef&&T[u].rig<=r){ 
        int cnt=upper_bound(T[u].sub,T[u].sub+r-l+1,h)-T[u].sub; 
        return cnt; 
    } 
    else{ 
        if(r<=T[lson].rig)return Query(lson,l,r,h); 
        if(l>=T[rson].lef)return Query(rson,l,r,h); 
        else return Query(lson,l,T[lson].rig,h)+Query(rson,T[rson].lef,r,h); 
    } 

 
int main(){ 
    int t,n,q; 
    scanf("%d",&t); 
    for(int cas=1;cas<=t;cas++){ 
 
        scanf("%d%d",&n,&q); 
        for(int i=1;i<=n;i++)scanf("%d",dat+i); 
 
        printf("Case %d:\n",cas); 
        Build(1,1,n); 
        int lf,rg,hg; 
        while(q--){ 
            scanf("%d%d%d",&lf,&rg,&hg); 
            printf("%d\n",Query(1,lf+1,rg+1,hg)); 
        } 
        finalizer(1,1,n); 
    } 


 

点击复制链接 与好友分享!回本站首页
相关TAG标签 杭州 网络
上一篇:HDOJ 4414 Finding crosses 搜索
下一篇:HDU 3544 Alice's Game
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站