线段树40pts求调

感激不尽

提交记录

#include <cstdio>
#define int long long

using namespace std;
template<typename T>
inline void in (T &x) {char c;int f=1;do {c=getchar ();if (c=='-') f=-1;} while (c>'9' || c<'0');for (x=0;c>='0' && c<='9';c=getchar ()) x=(x<<1)+(x<<3)+(c^48);x*=f;}
template<typename T>
inline void out (T x,char c) {if (x==0) {putchar ('0'),putchar (c); return ;}if (x<0) putchar ('-'),x=-x;int sta[20],k=0;while (x) sta[++k]=x%10,x/=10;while (k) putchar (sta[k--]+'0');putchar (c);}

const int N=1e6+10,oo=1<<60;
struct Segement {
    int l,r;
    int sum,alz,clz;
}tr[N<<2];
int a[N];
int n,q;
int op,x,y,k;

inline int max (const int &p,const int &q) {return p>q?p:q;}
inline void push_up (int p) {tr[p].sum=max (tr[p<<1].sum,tr[p<<1|1].sum);}
inline void c_push_down (int p) {
    if (tr[p].clz!=-oo) {
        tr[p<<1].alz=tr[p<<1|1].alz=0;
        tr[p<<1].clz=tr[p<<1|1].clz=tr[p].clz;
        tr[p<<1].sum=tr[p<<1|1].sum=tr[p].clz;
        tr[p].clz=-oo;
    }
}
inline void a_push_down (int p) {
    if (tr[p].alz) {
        c_push_down (p);
        tr[p<<1].sum+=tr[p].alz,tr[p<<1|1].sum+=tr[p].alz;
        tr[p<<1].alz+=tr[p].alz,tr[p<<1|1].alz+=tr[p].alz;
        tr[p].alz=0;
    }
}
inline void push_down (int p) {c_push_down (p),a_push_down (p);}
inline void build (int p,int l,int r) {
    tr[p].l=l,tr[p].r=r;
    if (l==r) {tr[p].sum=a[l],tr[p].clz=-oo,tr[p].alz=0; return ;}
    int mid=(l+r)/2;
    build (p<<1,l,mid);
    build (p<<1|1,mid+1,r);
    push_up (p);
}
inline void cmodify (int p,int l,int r,int k) {
    if (tr[p].l>=l && tr[p].r<=r) {tr[p].sum=k,tr[p].alz=0,tr[p].clz=k; return ;}
    push_down (p);
    if (tr[p<<1].r>=l) cmodify (p<<1,l,r,k);
    if (tr[p<<1|1].l<=r) cmodify (p<<1|1,l,r,k);
    push_up (p);
}
inline void amodify (int p,int l,int r,int k) {
    if (tr[p].l>=l && tr[p].r<=r) {
        c_push_down (p);
        tr[p].sum+=k,tr[p].alz+=k; 
        return ;
    }
    push_down (p);
    if (tr[p<<1].r>=l) amodify (p<<1,l,r,k);
    if (tr[p<<1|1].l<=r) amodify (p<<1|1,l,r,k);
    push_up (p);
}
inline int query (int p,int l,int r) {
    if (tr[p].l>=l && tr[p].r<=r) return tr[p].sum;
    push_down (p);
    int s=-oo;
    if (tr[p<<1].r>=l) s=max (s,query (p<<1,l,r));
    if (tr[p<<1|1].l<=r) s=max (s,query (p<<1|1,l,r));
    return s;
}
signed main () {
    in (n),in (q);
    for (int i=1;i<=n;++i) in (a[i]);
    build (1,1,n);
    for (int i=1;i<=n*4;++i) tr[i].clz=-oo;
    for (;q--;) {
        in (op);
        if (op==1) {in (x),in (y),in (k); cmodify (1,x,y,k);}
        if (op==2) {in (x),in (y),in (k); amodify (1,x,y,k);}
        if (op==3) {in (x),in (y); out (query (1,x,y),'\n');} 
    }
    return 0;
}