세그먼트 트리, 지연 전파

Question

이 구조체가 작동하는 방식과 업데이트하는 방법에 대한 좋은 생각이 있습니다.하지만 지연 전파와 함께 작동 할 때는 무엇을 해야할지 잘 모릅니다. 대회에 참가하십시오. 어떻게 작동시키는 지 알고 싶습니다.

내가 SPOJ에이 문제를 시도하고있다 : 누군가가 게으른 전파가 나는 그것을 받아 아이디어에서 작동이 상황에 적용 할 수있는 방법을 나에게 설명 할 수 있다면, 정말 게시하지 않으려는 http://www.spoj.com/problems/CDC12_H/

내 코드는 나를위한 아이디어가 나 자신에 의해이 작품을 만드는 것입니다하지만 약간의 도움이 있기 때문에.

누군가 내 문제에 대한 해결책을 제공하기를 바랍니다.

Answer 1

이것은 지연 전파가 포함 된 세그먼트 트리 구현의 내용입니다. 희망이 도움이 될 것입니다.

#define int long long 
#define MAX 100005*3 

int stree[MAX],lazy[MAX]; 

void update(int cur,int cur_lft,int cur_rgt,int st,int en,int val) 
{ 
    if(cur_lft>en || cur_rgt<st) return ; 
    if(cur_lft>=st && cur_rgt<=en) 
    { 
     stree[cur]+=val*(cur_rgt-cur_lft+1); 
     lazy[cur]+=val; 
     return; 
    } 
    int l=cur<<1,r=(cur<<1)+1,mid=(cur_lft+cur_rgt)>>1; 
    update(l,cur_lft,mid,st,en,val); 
    update(r,mid+1,cur_rgt,st,en,val); 
    stree[cur]=stree[l]+stree[r]+lazy[cur]*(cur_rgt-cur_lft+1); 
} 

int query(int cur,int cur_lft,int cur_rgt,int st,int en,int lzy) 
{ 
    if(cur_lft>en || cur_rgt<st) return 0; 
    if(cur_lft>=st && cur_rgt<=en) return stree[cur]+lzy*(cur_rgt-cur_lft+1); 
    int l=cur<<1,r=(cur<<1)+1,mid=(cur_lft+cur_rgt)>>1; 
    int left_tree=query(l,cur_lft,mid,st,en,lzy+lazy[cur]); 
    int right_tree=query(r,mid+1,cur_rgt,st,en,lzy+lazy[cur]); 
    return left_tree+right_tree; 
} 

업데이트 및 세그먼트 트리에 쿼리 우리는 다음과 같은 기능을 호출 할 수 있습니다 편집 :

query(1,0,n-1,lower_range,upper_range,0)); 
update(1,0,n-1,lower_range,upper_range,v); 

을