60,求大佬指点一二

P1253 扶苏的问题

tyz090617 @ 2024-08-07 22:34:06

#include<bits/stdc++.h>
#include<vector>
#include<map>
#define int long long
#define maxn 1e18
using namespace std;
void build_sg(int q,int l,int r);
inline void lazy_up_sg(int q);
void revinter_sg(int q,int x,int y,int z);
int findp_sg(int q,int x);
inline void lazy_down_sg(int q);
int findmax_sg(int q,int x,int y);
void revinterv_sg(int q,int x,int y,int z);
struct segment_tree{
    int l,r;
    int mv;
}segtree[10000005]; 
 inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }return x*f;
}
int treesize,tz,fr[10000005],siz,tag[10000005]={},tagv[1000005];
bool kk[10000005];
int a,b,c,d,e,f,g; 
signed main(){
    cin>>a>>b; 
    for(int i=1;i<=a;i++){
        fr[i]=read();
    }treesize=tz=2*a-1;siz=a;
    build_sg(1,1,siz);
    for(int i=1;i<=b;i++){
        c=read();
        if(c==2){
            d=read();e=read();f=read();
            revinter_sg(1,d,e,f);
        //  errtr_sg();
        }else if(c==1){
            d=read();e=read();f=read();
        revinterv_sg(1,d,e,f);//errtr_sg();
        }else{
            d=read();e=read();
            cout<<findmax_sg(1,d,e)<<endl;
        }
    }
    return 0;
}
void revinterv_sg(int q,int x,int y,int z){
    if(x<=segtree[q].l&&segtree[q].r<=y) {
        if(tag[q])lazy_down_sg(q);
        segtree[q].mv=z;
        tagv[q]=z;
        tag[q]=0;
        kk[q]=1;
        return ;
    }
    lazy_down_sg(q);
    int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1;
    if(x<=mid)revinterv_sg(u,x,y,z);
    if(y>mid)revinterv_sg(u+1,x,y,z);
    lazy_up_sg(q);

}
void revinter_sg(int q,int x,int y,int z){
    if(x<=segtree[q].l&&segtree[q].r<=y) {
        if(kk[q])lazy_down_sg(q);
        segtree[q].mv+=z;
        tag[q]+=z;
        return ;
    }
    lazy_down_sg(q);
    int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1;
    if(x<=mid)revinter_sg(u,x,y,z);
    if(y>mid)revinter_sg(u+1,x,y,z);
    lazy_up_sg(q);

}
int findmax_sg(int q,int x,int y){
    if(x<=segtree[q].l&&segtree[q].r<=y) {
    return segtree[q].mv;
    }
    lazy_down_sg(q);
    int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1,ans=-maxn;
    if(x<=mid)ans=max(findmax_sg(u,x,y),ans);
    if(y>mid)ans=max(findmax_sg(u+1,x,y),ans);
    lazy_up_sg(q);
    return ans;
}
 void lazy_down_sg(int q){
    if(kk[q]){
        int u=q<<1,l=segtree[q].l,r=segtree[q].r;
        int mid=(l+r)>>1;
        tagv[u]=tagv[q];
        tagv[u+1]=tagv[q];
        kk[u]=1;
        kk[u+1]=1;
        segtree[u].mv=tagv[q];
        segtree[u+1].mv=tagv[q];
        //tagv_check(q,u);
        tagv[q]=0;
        kk[q]=0;
    }
    if(tag[q]){
        int u=q<<1,l=segtree[q].l,r=segtree[q].r;
        int mid=(l+r)>>1;
        tag[u]+=tag[q];
        tag[u+1]+=tag[q];
        segtree[u].mv+=tag[q];
        segtree[u+1].mv+=tag[q];
        tag[q]=0;
    }

}
void lazy_up_sg(int q){
    int u=q<<1;
    segtree[q].mv=max(segtree[u].mv,segtree[u+1].mv);
}
void build_sg(int q,int l,int r){
    segtree[q].l=l;segtree[q].r=r;
    if(l==r){
        segtree[q].mv=fr[l];
        return ;
    }int mid=(l+r)>>1,u=q<<1;
    build_sg(u,l,mid);
    build_sg(u+1,mid+1,r);
    lazy_up_sg(q);
}

|