总分60分，求调

hamster000 @ 2024-08-03 08:20:45

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e6+10;
int null=LONG_LONG_MAX;
struct node{
    int lazy1,lazy2;//赋值的优先级在加法前面
    int val,l,r;
}tr[maxn*4];
int a[maxn];

void pushup(int rt){
    tr[rt].val=max(tr[rt*2].val,tr[rt*2+1].val);
}

inline void coverdown(int rt)
{
    if(tr[rt].lazy1!=null)
    {
        tr[rt*2].lazy2=tr[rt*2+1].lazy2=0;
        tr[rt*2].val=tr[rt*2+1].val=tr[rt].lazy1;
        tr[rt*2].lazy1=tr[rt*2+1].lazy1=tr[rt*2].lazy1;
        tr[rt].lazy1=null;
    }
}

inline void sumdown(int rt)
{
    if(tr[rt].lazy2)
    {
        coverdown(rt);
        tr[rt*2].val+=tr[rt].lazy2,tr[rt*2+1].val+=tr[rt].lazy2;
        tr[rt*2].lazy2+=tr[rt].lazy2,tr[rt*2+1].lazy2+=tr[rt].lazy2;
        tr[rt].lazy2=0;
    }
}
inline void pushdown(int rt)
{
    coverdown(rt);
    sumdown(rt);
}
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r){
        tr[rt].val=a[l];
        tr[rt].lazy1=null;
        tr[rt].lazy2=0;
        return ;
    }
    int mid=(l+r)/2;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    pushup(rt);
}

void modify(int rt,int x,int y,int k){//区间赋值为k
    int l=tr[rt].l,r=tr[rt].r;
    if(x<=l&&r<=y){
        tr[rt].lazy2=0;
        tr[rt].lazy1=tr[rt].val=k;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)/2;
    if(x<=mid) modify(rt*2,x,y,k);
    if(y>mid) modify(rt*2+1,x,y,k);
    pushup(rt);
}

void update(int rt,int x,int y,int k){
    int l=tr[rt].l,r=tr[rt].r;
    if(x<=l&&r<=y){
        pushdown(rt);
        //tr[rt].lazy2+=k;
        tr[rt].lazy2+=k;
        tr[rt].val+=k;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)/2;
    if(x<=mid) update(rt*2,x,y,k);
    if(y>mid) update(rt*2+1,x,y,k);
    pushup(rt);
}

int query(int rt,int x,int y){
    int l=tr[rt].l,r=tr[rt].r;
    if(r<x||l>y) return LONG_LONG_MIN;
    if(x<=l&&r<=y){
        return tr[rt].val;
    }
    pushdown(rt);
    int mid=(l+r)/2,ans=LONG_LONG_MIN;
    if(x<=mid) ans=max(ans,query(rt*2,x,y));
    if(y>mid) ans=max(ans,query(rt*2+1,x,y));
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    build(1,1,n);
    for(int i=1;i<=n*4;i++) tr[i].lazy1=null;
    while(q--){
        int op,x,y;
        cin >> op >> x >> y;
        if(op==1){
            int k;
            cin >> k;
            modify(1,x,y,k);
        }if(op==2){
            int k;
            cin >> k;
            update(1,x,y,k);
        }if(op==3){
            cout << query(1,x,y) << endl;
        }
    }
}

by tyz090617 @ 2024-08-07 22:26:10

我也60，哈哈哈

by tjyqwq @ 2024-10-07 16:12:00

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NUM=1e6+6;
const int INF=1e16;
int n,m;
int a[NUM],lazytag1[NUM<<2],tree[NUM<<2],lazytag2[NUM<<2];
int lc(int root){
    return root<<1;
}
int rc(int root){
    return (root<<1)+1;
}
void pushup(int root){
    tree[root]=max(tree[lc(root)],tree[rc(root)]);
}
void build(int root,int l,int r){
    if(l==r){
        tree[root]=a[l];
        return;
    }
    lazytag1[root]=INF;//初始化！！！ 
    int mid=(l+r)>>1;
    build(lc(root),l,mid);
    build(rc(root),mid+1,r);
    pushup(root);
}
void addtag1(int root,int l,int r,int k){
    lazytag1[root]=k; lazytag2[root]=0;
    tree[root]=k;
}
void addtag2(int root,int l,int r,int k){
    lazytag2[root]+=k; tree[root]+=k;
}
void pushdown1(int root,int l,int r){
    if(lazytag1[root]!=INF){
        int mid=(l+r)>>1;
        addtag1(lc(root),l,mid,lazytag1[root]);
        addtag1(rc(root),mid+1,r,lazytag1[root]);
        lazytag1[root]=INF;
    }
}
void pushdown2(int root,int l,int r){
    if(lazytag2[root]){
        int mid=(l+r)>>1;
        addtag2(lc(root),l,mid,lazytag2[root]);
        addtag2(rc(root),mid+1,r,lazytag2[root]);
        lazytag2[root]=0;
    }
}
void pushdown(int root,int l,int r){
    pushdown1(root,l,r);
    pushdown2(root,l,r);
    //不要写反了！！ 
}
void update1(int root,int l,int r,int ql,int qr,int k){
    if(ql<=l&&qr>=r){//能覆盖,停下 
        addtag1(root,l,r,k); return;
    }
    pushdown(root,l,r);//不能覆盖,往下传 
    int mid=(l+r)>>1;
    if(ql<=mid) update1(lc(root),l,mid,ql,qr,k);
    if(qr>mid) update1(rc(root),mid+1,r,ql,qr,k);
    pushup(root);
}
void update2(int root,int l,int r,int ql,int qr,int k){
    if(ql<=l&&qr>=r){//能覆盖,停下 
        addtag2(root,l,r,k); return;
    }
    pushdown(root,l,r);//不能覆盖,往下传 
    int mid=(l+r)>>1;
    if(ql<=mid) update2(lc(root),l,mid,ql,qr,k);
    if(qr>mid) update2(rc(root),mid+1,r,ql,qr,k);
    pushup(root);
}
int query(int root,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return tree[root];
    pushdown(root,l,r);
    int mid=(l+r)>>1; int ans=-INF;
    if(ql<=mid) ans=max(ans,query(lc(root),l,mid,ql,qr));
    if(qr>mid) ans=max(ans,query(rc(root),mid+1,r,ql,qr));
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int op; cin>>op;
        if(op==1){
            int lb,rb,k; cin>>lb>>rb>>k;
            update1(1,1,n,lb,rb,k);
        }
        else if(op==2){
            int lb,rb,k; cin>>lb>>rb>>k;
            update2(1,1,n,lb,rb,k);
        }
        else if(op==3){
            int lb,rb; cin>>lb>>rb;
            cout<<query(1,1,n,lb,rb)<<"\n";
        }
    }
    return 0;
}