程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-4325-Flowers

HDU-4325-Flowers

編輯:C++入門知識

成段更新加離散化線段樹

這題做了快有一天了。。。。各種問題啊,開始建樹時沒有把查詢的節點加入樹中,結果在查詢時發現很多節點的信息丟失了,糾結了半天去看了下別人的代碼,原來建樹時就應把查詢的節點加入,在做離散化時,將hash數組開到10^9,又超內存了,通不過編譯,囧,之後改成map映射,終於羞愧的A了(這題的數據可能比較弱,不加離散化也能過)


[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<algorithm> 
#include<vector> 
#include<map> 
using namespace std; 
#define N 100005 
map<int,int>h; 
int x[3*N]; //要加上查詢的節點 
int  ask[N]; 
struct cam2 

    int x; 
    int y; 
}flower[N*2]; 
struct cam1 

    int x; 
    int y; 
    int sum; 
    int add; 
}list[N*4]; 
void build(int k,int x,int y) 

    int mid; 
    list[k].add=0; 
    list[k].x=x; 
    list[k].y=y; 
    list[k].sum=0; 
    if(list[k].x==list[k].y) 
    return; 
    mid=(x+y)/2; 
    build(k<<1,x,mid); 
    build(k<<1|1,mid+1,y); 

void update(int k,int x,int y,int d) 

    int mid; 
    if(list[k].x==x&&list[k].y==y) 
    { 
        list[k].sum+=(list[k].y-list[k].x+1)*d; 
        list[k].add+=d; 
        return; 
    } 
    if(list[k].add!=0) 
    { 
        list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add; 
        list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add; 
        list[k<<1].add+=list[k].add; 
        list[k<<1|1].add+=list[k].add; 
        list[k].add=0; 
    } 
    mid=(list[k].x+list[k].y)/2; 
    if(x>mid) 
    update(k<<1|1,x,y,d); 
    else if(y<=mid) 
    update(k<<1,x,y,d); 
    else 
    { 
        update(k<<1,x,mid,d); 
        update(k<<1|1,mid+1,y,d); 
    } 
    list[k].sum=list[k<<1].sum+list[k<<1|1].sum; 

int find(int k,int x,int y) 

    int mid; 
    if(list[k].x==x&&list[k].y==y) 
    return list[k].sum; 
    if(list[k].add!=0) 
    { 
        list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add; 
        list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add; 
        list[k<<1].add+=list[k].add; 
        list[k<<1|1].add+=list[k].add; 
        list[k].add=0; 
    } 
    mid=(list[k].x+list[k].y)/2; 
    if(x>mid) 
    return find(k<<1|1,x,y); 
    else if(y<=mid) 
    return find(k<<1,x,y); 
    return find(k<<1,x,mid)+find(k<<1|1,mid+1,y); 

int main() 

    int k,t,n,m,i,cnt,num; 
    scanf("%d",&t); 
    for(k=1;k<=t;k++) 
    { 
        scanf("%d%d",&n,&m); 
        cnt=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d",&flower[i].x,&flower[i].y); 
            x[cnt++]=flower[i].x; 
            x[cnt++]=flower[i].y; 
        } 
        printf("Case #%d:\n",k); 
        for(i=0;i<m;i++)  //建樹時就將要查詢的節點插入,否則在查詢時會丟失節點信息 
        { 
            scanf("%d",&ask[i]); 
            x[cnt++]=ask[i]; 
        } 
        sort(x,x+cnt); 
        cnt=unique(x,x+cnt)-x; 
        h.clear(); 
        for(i=0;i<cnt;i++)  //減小建樹的空間 
        h[x[i]]=i; 
        build(1,0,cnt-1); 
        for(i=n-1;i>=0;i--) 
        update(1,h[flower[i].x],h[flower[i].y],1); 
        for(i=0;i<m;i++) www.2cto.com
        printf("%d\n",find(1,h[ask[i]],h[ask[i]])); 
    } 
    return 0; 

 


作者:Cambridgeacm

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved