求求求求大佬们帮帮我,谢谢

P1253 扶苏的问题

gmx0424 @ 2023-11-01 23:22:04

#include<bits/stdc++.h>
using namespace std;
#define  ll long long
#define INF 1e11;
int n, q;
const int maxn = 1e6 + 5;
ll a[maxn], val[maxn << 2], add[maxn << 2],  re[maxn << 2];
bool flag[maxn << 2];//标记是否要修改 

inline int read() {
    int ans=0,op=1;
    char c = getchar();
    while(c<'0'|| c>'9') {
        if (c == '-'){
            op = -1;
        }
        c=getchar();
    }
    while(c>='0'&& c<='9'){
        ans = ans * 10 + c - '0';
        c=getchar();
    }
    return ans * op;
}

void pushdown(int rt){
    if (flag[rt] ){
        flag[rt<<1] = true; //修改标记 
        flag[rt<<1|1] = true;

        add[rt<<1] = 0;//修改加法-子节点清空 
        add[rt<<1|1] = 0;

        re[rt<<1] = re[rt];//修改覆盖 
        re[rt<<1|1] = re[rt];

        val[rt<<1] = re[rt];//修改最大值 
        val[rt<<1|1] = re[rt];

        flag[rt] = false;
    }   
    if (add[rt]) {
        add[rt<<1] += add[rt];
        add[rt<<1|1] += add[rt];
        val[rt<<1] += add[rt];
        val[rt<<1|1] += add[rt];
        add[rt] = 0;

    }
}

void pushup(int rt){
    val[rt] == max (val[rt << 1] ,val[rt << 1 | 1] );
}

void build (int rt, int l, int r){
    flag[rt] = false;
    add[rt] = 0;
    if (l == r) {
        val[rt] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void rev(int rt, int l, int r, int ql, int qr, ll k){
    if (qr < l || ql > r){
        return ;
    }
    if (ql <= l && r <= qr){
        re[rt] = k;
        add[rt] = 0;
        val[rt] = k;
        flag[rt] = true;
        return ;
    }
    pushdown(rt);
    int mid = (l + r)>>1;
    rev(rt<<1,l,mid,ql,qr,k);
    rev(rt<<1|1,mid+1,r,ql,qr,k);
    pushup(rt);
}

void update(int rt, int l, int r, int ql, int qr, ll k){
    if (qr < l || ql > r){
        return ;
    }
    if (ql <= l && r <= qr){
        add[rt] += k;
        val[rt] += k;
        return ;
    }
    pushdown(rt);
    int mid = (l + r)>>1;
    update(rt<<1,l,mid,ql,qr,k);
    update(rt<<1|1,mid+1,r,ql,qr,k);
    pushup(rt);
}

ll ask(int rt, int l, int r, int ql, int qr){
    if (qr<l||ql>r){
        return 0;
    }
    if(ql<=l&&r<=qr){
        return val[rt];
    }
    pushdown(rt);
    int mid = (l+r)>>1;
    ll res = -INF;
    res = max(res,ask(rt<<1,l,mid,ql,qr));
    res = max(res,ask(rt<<1|1,mid+1,r,ql,qr));
    return res;
}

int main () {
    n=read(), q=read();
    for (int i = 1; i <= n; i++){
         a[i] = read();
    }
    build(1,1,n);
    while (q--){
        int op ;
        op=read();
        if(op == 1){
            int l, r;
            ll x;
            l=read();
            r=read();
            x=read();
            rev(1,1,n,l,r,x);//修改 
        }else if(op==2){
            int l, r;
            ll x;
            l=read();
            r=read();
            x=read();
            update(1,1,n,l,r,x);
        }else {
            int l, r;
            l=read();
            r=read();
            cout << ask(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
}

|