# SMT 90pts求助,最后一个WA

P1253 扶苏的问题

hiro653 @ 2023-02-22 13:59:06

//洛谷 P3372,线段树,区间修改 + 区间查询
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
#define INF 209833298937876897
ll a[N];        //记录数列的元素,从a[1]开始
ll tree[N<<2];  //tree[i]:第i个结点的值,表示一个线段区间的值,例如最值、区间和
ll tag_chg[N<<2];   //tag[i]:第i个结点的lazy-tag,统一记录这个区间的修改
ll tag_add[N<<2];
ll ls(ll p){ return p<<1;  }           //定位左儿子:p*2
ll rs(ll p){ return p<<1|1;}           //定位右儿子:p*2 + 1
//const long long  INF=  0x3f3f3f3f3f3f3f;
void push_up(ll p){                    //从下往上传递区间值
     tree[p] = max(tree[ls(p)], tree[rs(p)]);
}

void build(ll p,ll pl,ll pr){    //建树。p是结点编号,它指向区间[pl, pr]                       //lazy-tag标记
    tag_chg[p]=-INF;
    if(pl==pr){tree[p]=a[pl]; return;}  //最底层的叶子,赋值    
    ll mid = (pl+pr) >> 1;              //分治:折半
    build(ls(p),pl,mid);                //左儿子
    build(rs(p),mid+1,pr);              //右儿子
    push_up(p);                         //从下往上传递区间值
} 

void make_tag(ll p){

    if(tag_chg[p]!=-INF)tree[p]=tag_chg[p]+tag_add[p];
    else tree[p]+=tag_add[p];
}

void cvr_down(ll p){

    if(tag_chg[p]!=-INF){

        tag_chg[ls(p)]=tag_chg[rs(p)]=tag_chg[p]+tag_add[p];
        tag_add[ls(p)]=tag_add[rs(p)]=0;
        make_tag(ls(p));
        make_tag(rs(p));
        tag_chg[p]=-INF;
        tag_add[p]=0;

    }
}

void sum_down(ll p){

if(tag_add[p]){
    cvr_down(ls(p));
    cvr_down(rs(p));
    tag_add[ls(p)]+=tag_add[p];
    tag_add[rs(p)]+=tag_add[p];
    tree[ls(p)]+=tag_add[p];
    tree[rs(p)]+=tag_add[p];
    tag_add[p]=0;
}

}

void push_down(ll p){

     cvr_down( p);
     sum_down(p);

}
void update_add(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改:把[L, R]内每个元素加上d
    if(L<=pl && pr<=R){       //完全覆盖,直接返回这个结点,它的子树不用再深入了    

      tag_add[p]+=d;
      tree[p]+=d;
      return;                    
    }
    //如果不能覆盖,表示该区间的一致性遭到破坏,先push_down把tag传给子树
    push_down(p);          
    ll mid=(pl+pr)>>1;
    if(L<=mid) update_add(L,R,ls(p),pl,mid,d);    //递归左子树
    if(R>mid)  update_add(L,R,rs(p),mid+1,pr,d);  //递归右子树
     //至此左右子树都已经更新,push_up更新parent
    push_up(p);                              
}
void update_chg(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改:把[L, R]内每个元素加上d
    if(L<=pl && pr<=R){       //完全覆盖,直接返回这个结点,它的子树不用再深入了    

        tree[p]=d;  
        tag_chg[p]=d;
        tag_add[p]=0;
        return;                    
    }
    //如果不能覆盖,表示该区间的一致性遭到破坏,先push_down把tag传给子树
    push_down(p);                 
    ll mid=(pl+pr)>>1;
    if(L<=mid) update_chg(L,R,ls(p),pl,mid,d);    //递归左子树
    if(R>mid)  update_chg(L,R,rs(p),mid+1,pr,d);  //递归右子树
     //至此左右子树都已经更新,push_up更新parent
    push_up(p);                              
}

ll query(ll L,ll R,ll p,ll pl,ll pr){
  //查询区间[L,R];p是当前结点(线段)的编号,[pl,pr]是结点p表示的线段区间
    if(pl>=L && R >= pr) {
        return tree[p];       //完全覆盖,直接返回
    }
    push_down(p);                        //不能覆盖,递归子树
    ll res=-INF;
    ll mid = (pl+pr)>>1;
    if(L<=mid) res=max(res,query(L,R,ls(p),pl,mid));   //左子结点有重叠
    if(R>mid)  res=max(res,query(L,R,rs(p),mid+1,pr)); //右子结点有重叠
    return res;
}

int main(){
    ll n, m;  scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)  scanf("%lld",&a[i]);
    build(1,1,n);                              //建树
    while(m--){
        ll q,L,R,d;  

        scanf("%lld",&q);
        if (q==1){                          //区间修改:把[L,R]的每个元素加上d
            scanf("%lld %lld %lld",&L,&R,&d);
            update_chg(L,R,1,1,n,d); 
        }else if(q==2){

            scanf("%lld %lld %lld",&L,&R,&d);
            update_add(L,R,1,1,n,d); 
        }
        else {                                 //区间询问:[L,R]的区间和
            scanf("%lld %lld",&L,&R);
            printf("%lld\n",query(L,R,1,1,n));   
        }       
    }
    return 0;
}

|