UOJ 164 V線分樹lazy(メンテナンス履歴の値)

一列数の維持、サポート:1.区間プラスA 2.区間マイナスA、減算終了後の各位置と0はmax 3を取ります.区間はA 4をカバーします.質問票の現在値5.質問票の履歴の一番値を聞きます.
線分樹のlazylは4つの配列を記録します.転移と初期条件に注意してください.

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=10000010;
const LL INF=1e18;
int n,m;
struct Tree{
    LL add,addmax,r,rmax;
}tree[maxn<<2],tmp;
int qx;
int ql,qr;
int type;
LL s[maxn];
void build(int o,int l,int r){
    if(l==r){
        tree[o]=(Tree){0,0,-INF,-INF};
        return;
    }
    int lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
}
Tree update(Tree u,Tree v){
    return (Tree){
        max(u.add+v.add,-INF),max(u.addmax,u.add+v.addmax),max(u.r+v.add,v.r),max(max(u.rmax,v.rmax),u.r+v.addmax)
    };
}
void pushdown(int o){
    tree[o<<1]=update(tree[o<<1],tree[o]);
    tree[o<<1|1]=update(tree[o<<1|1],tree[o]);
    tree[o]=(Tree){0,-INF,0,-INF};
}
void change(int o,int l,int r){
    if(ql<=l && qr>=r){
        tree[o]=update(tree[o],tmp);
        return;
    }
    pushdown(o);
    int lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
    if(ql<=mid) change(lc,l,mid);
    if(qr>mid) change(rc,mid+1,r);
}
void query(int o,int l,int r){
    if(l==r){
        if(type==4) printf("%lld
",max(tree[o].add+s[qx],tree[o].r));
        if(type==5) printf("%lld
",max(tree[o].addmax+s[qx],tree[o].rmax));
        return;
    }
    pushdown(o);
    int lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
    if(qx<=mid) query(lc,l,mid);
    else query(rc,mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&s[i]);
    build(1,1,n);
    while(m--){
        scanf("%d",&type);
        int x;
        if(type<=3){
            scanf("%d%d",&ql,&qr);
            scanf("%d",&x);
            if(type==1)tmp=(Tree){x,x,-INF,-INF};
            if(type==2)tmp=(Tree){-x,-x,0,0};
            if(type==3)tmp=(Tree){-INF,-INF,x,x};
            change(1,1,n);
        }else{
            scanf("%d",&qx);
            query(1,1,n);
        }
    }
    return 0;
}

^_^