20pts求调，AC in #1#3

All_Wrong_Answer @ 2024-12-05 18:31:23

by All_Wrong_Answer @ 2024-12-05 18:32:07

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int l;
    int r;
    int s;
    int add;
    int use;
}tre[4000005];
int m[1000005];
void js(int q,int l,int r){
    tre[q].l=l;
    tre[q].r=r;
    tre[q].s=m[l];
    tre[q].add=0;
    tre[q].use=0;
    if(l==r) return ;
    int mid=(l+r)/2;
    js(q*2,l,mid);
    js(q*2+1,mid+1,r);
    tre[q].s=max(tre[q*2].s,tre[q*2+1].s);
}
void pushuse(int q){
    if(tre[q].use!=0){
        tre[q*2].s=tre[q].s;
        tre[q*2+1].s=tre[q].s;
        tre[q*2].use=tre[q].use;
        tre[q*2+1].use=tre[q].use;
        tre[q].use=0;
    }
}
void pushadd(int q){
    if(tre[q].add!=0){
        tre[q*2].s+=tre[q].add;
        tre[q*2+1].s+=tre[q].add;
        tre[q*2].add=tre[q].add;
        tre[q*2+1].add=tre[q].add;
        tre[q].add=0;
    }
}
void qjxg(int q,int ml,int mr,int k){
    if(tre[q].l>=ml&&tre[q].r<=mr){
        tre[q].s=k;
        tre[q].use=1;
        pushuse(q);
        return ;
    }
    pushuse(q);
    int mid=(tre[q].l+tre[q].r)/2;
    if(ml<=mid) qjxg(q*2,ml,mr,k);
    if(mr>mid) qjxg(q*2+1,ml,mr,k);
    tre[q].s=max(tre[q*2].s,tre[q*2+1].s);
    return ;
}
void qjjf(int q,int ml,int mr,int k){
    if(tre[q].l>=ml&&tre[q].r<=mr){
        tre[q].s+=k;
        tre[q].add=k;
        pushadd(q);
        return ;
    }
    pushadd(q);
    int mid=(tre[q].l+tre[q].r)/2;
    if(ml<=mid) qjjf(q*2,ml,mr,k);
    if(mr>mid) qjjf(q*2+1,ml,mr,k);
    tre[q].s=max(tre[q*2].s,tre[q*2+1].s);
    return ;
}
int qjzd(int q,int ml,int mr){
    pushadd(q);
    pushuse(q);

    //cout<<q<<" "<<tr[q].l<<" "<<tr[q].r<<" "<<tr[q].sum<<"\n";
    if(tre[q].l>=ml&&tre[q].r<=mr) return tre[q].s;
    long long mid=(tre[q].l+tre[q].r)/2;
    long long summ=0;
    if(/*tre[q].l<=ml*/ml<=mid/*&&tre[q].r>=mr*/){
        summ= max(summ,qjzd(q*2,ml,mr));
    }
    if(/*tre[q].l>=ml&&*/mr>mid/*tre[q].r>=mr*/){
        summ= max(summ,qjzd(q*2+1,ml,mr));
    }
    return summ;
}
signed main(){
    int x,y,u,a,b,c;
    scanf("%lld%lld",&x,&y);
    for(int i=1;i<=x;i++){
        scanf("%lld",&m[i]);
    }
    js(1,1,x);
    for(int i=1;i<=y;i++){
        cin>>u;
        if(u==1){
            cin>>a>>b>>c;
            qjxg(1,a,b,c);
        }
        if(u==2){
            cin>>a>>b>>c;
            qjjf(1,a,b,c);
        }
        if(u==3){
            cin>>a>>b;
            cout<<qjzd(1,a,b)<<endl;
        }
    }
    return 0;
}