当前位置：首页 > news >正文

poj 3468(线段树+lazy思想)

news 来源：原创 2024/5/19 1:00:28

题目链接：http://poj.org/problem?id=3468

思路：如果直接去做，每次都更新到叶子节点，那必然会TLE，我们可以采用lazy的思想：没必要每次更新都更新到叶子节点，只要有一个合适的范围就用一个增量来记录它，当下一次询问时，如果这个范围正好合适询问的范围，就直接是这个节点的sum值加上这个区间长度*lnc，再加到总和上去，若这个节点的范围不适合所要查询的范围，那么就要查询它的子节点，这个时候再把增量传给她的子节点，并且清空父亲节点的增量，这样效率能大大提高。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define MAXN 100010
  7 typedef long long ll;
  8 
  9 struct Node{
 10     int L,R;
 11     ll lnc;//增量
 12     ll sum;
 13 }node[MAXN<<2];
 14 
 15 int N,Q;
 16 
 17 void Build(int L,int R,int rt)
 18 {
 19     if(L==R){
 20         node[rt].lnc=node[rt].sum=0;
 21         return ;
 22     }
 23     node[rt].lnc=node[rt].sum=0;
 24     int M=(L+R)>>1;
 25     Build(L,M,rt<<1);
 26     Build(M+1,R,(rt<<1)|1);
 27 }
 28 
 29 void Updata(int L,int R,int rt,int id,ll x)
 30 {
 31     if(L==id&&R==id){
 32         node[rt].sum=x;
 33         return ;
 34     }
 35     node[rt].sum+=x;
 36     int M=(L+R)>>1;
 37     if(id<=M){
 38         Updata(L,M,rt<<1,id,x);
 39     }else 
 40         Updata(M+1,R,(rt<<1)|1,id,x);
 41 }
 42 
 43 void Add_Updata(int L,int R,int rt,int l,int r,ll x)
 44 {
 45     if(l<=L&&R<=r){
 46         node[rt].lnc+=x;//若此节点所在区段被包含在要插入的区段中，就将插入值存在lnc中，return;
 47         return ;
 48     }else if(L<=l&&r<=R){
 49         node[rt].sum+=(r-l+1)*x;
 50     }else if(L>=l&&R>=r){
 51         node[rt].sum+=(r-L+1)*x;
 52     }else if(L<=l&&R<=r){
 53         node[rt].sum+=(R-l+1)*x;
 54     }
 55     int M=(L+R)>>1;
 56     if(r<=M){
 57         Add_Updata(L,M,rt<<1,l,r,x);
 58     }else if(l>M){
 59         Add_Updata(M+1,R,(rt<<1)|1,l,r,x);
 60     }else {
 61         Add_Updata(L,M,rt<<1,l,r,x);
 62         Add_Updata(M+1,R,(rt<<1)|1,l,r,x);
 63     }
 64 }
 65 
 66 ll sum;
 67 void Query(int L,int R,int rt,int l,int r)
 68 {
 69     if(l<=L&&R<=r){
 70         sum+=node[rt].sum+node[rt].lnc*(R-L+1);
 71         return ;
 72     }
 73     //若上面if条件不成立，则要询问它的子节点，此时增量要下传，并且要更新其本身的sum;
 74     node[rt<<1].lnc+=node[rt].lnc;
 75     node[(rt<<1)|1].lnc+=node[rt].lnc;
 76     node[rt].sum+=node[rt].lnc*(R-L+1);
 77     node[rt].lnc=0;
 78     int M=(L+R)>>1;
 79     if(r<=M){
 80         Query(L,M,rt<<1,l,r);
 81     }else if(l>M){
 82         Query(M+1,R,(rt<<1)|1,l,r);
 83     }else {
 84         Query(L,M,rt<<1,l,r);
 85         Query(M+1,R,(rt<<1)|1,l,r);
 86     }
 87 }
 88 
 89 int main()
 90 {
 91     int a,b,c;
 92     char str[11];
 93     scanf("%d%d",&N,&Q);
 94     Build(1,N,1);
 95     for(int i=1;i<=N;i++){
 96         scanf("%d",&a);
 97         Updata(1,N,1,i,(ll)a);
 98     }
 99     while(Q--){
100         scanf("%s",str);
101         if(str[0]=='Q'){
102             scanf("%d%d",&a,&b);
103             sum=0;
104             Query(1,N,1,a,b);
105             printf("%lld\n",sum);
106         }else {
107             scanf("%d%d%d",&a,&b,&c);
108             Add_Updata(1,N,1,a,b,(ll)c);
109         }
110     }
111     return 0;
112 }
113  
114 
115