萌新WA+TLE求调

P1253 扶苏的问题 萌新WA+TLE(20points)求调

#include <cstdio>
#include <iostream>
#define lson rt*2, l, md
#define rson rt*2+1, md+1, r
using namespace std;

typedef long long ll;
const ll N = 1e6 + 10, INF = -114514919810;
ll n, q, a[N], xds[N*4], tag1[N*4], tag2[N*4];

void build(int rt, int l, int r){
    if (l == r){
        xds[rt] = a[l];
        return;
    }
    int md = (l + r) >> 1;
    build(lson);
    build(rson);
    xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

void cover(int rt){
    if (tag1[rt] != INF){
        xds[rt*2] = xds[rt*2+1] = tag1[rt];
        tag1[rt*2] = tag1[rt*2+1] = tag1[rt];
        tag2[rt*2] = tag2[rt*2+1] = 0;
        tag1[rt] = INF;
    }
}

void pushdown(int rt){
    cover(rt);
    if (tag2[rt]){
        xds[rt*2] += tag2[rt];
        xds[rt*2+1] += tag2[rt];
        tag2[rt*2] += tag2[rt];
        tag2[rt*2+1] += tag2[rt];
        tag2[rt] = 0;
    }
}

void update1(int rt, int l, int r, int x, int y, ll k){
    if (x <= l && r <= y){
        xds[rt] = k;
        tag1[rt] = k;
        tag2[rt] = 0;
        return;
    }
    pushdown(rt);
    int md = (l + r) >> 1;
    if (md >= x)    update1(lson, x, y, k);
    if (md < y) update1(rson, x, y, k);
    xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

void update2(int rt, int l, int r, int x, int y, ll k){
    if (x <= l && r <= y){
        cover(rt);
        xds[rt] += k;
        tag2[rt] += k;
        return;
    }
    pushdown(rt);
    int md = (l + r) >> 1;
    if (md >= x)    update2(lson, x, y, k);
    if (md < y) update2(rson, x, y, k);
    xds[rt] = max(xds[rt*2], xds[rt*2+1]);
}

ll query(int rt, int l, int r, int x, int y){
    if (x <= l && r <= y)
        return xds[rt];
    pushdown(rt);
    ll ans = -INF;
    int md = (l + r) >> 1;
    if (md >= x)    ans = max(ans, query(lson, x, y));
    if (md < y) ans = max(ans, query(rson, x, y));
    return ans;
}

int main(){
    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++)
        tag1[i] = INF;

    for (int i = 1; i <= q; i++){
        int op;
        cin >> op;
        if (op == 1){
            ll x, y, z;
            cin >> x >> y >> z;
            update1(1, 1, n, x, y, z);
        }else if (op == 2){
            ll x, y, z;
            cin >> x >> y >> z;
            update2(1, 1, n, x, y, z);
        }else{
            ll x, y;
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << endl;
        }
    }

    return 0;
}