求调,只通过1,3点,其余WA没有TLE或RE

P1253 扶苏的问题

Prolystic @ 2024-02-09 23:32:03

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5; 
const ll ctg_ex = -0x7f7f7f7f7f7f7f7f; // 标记覆盖标记不存在的数字
ll n, q;
ll a[N], ans[N << 2], covertag[N << 2], addtag[N << 2];
inline ll ls(ll p) { return p << 1; }
inline ll rs(ll p) { return p << 1 | 1; }
inline void push_up(ll p) { ans[p] = max(ans[ls(p)], ans[rs(p)]); }
void build(ll p, ll l, ll r){
    covertag[p] = ctg_ex, addtag[p] = 0;
    if(l == r)
        ans[p] = a[l];
    else{
        ll mid = l + r >> 1;
        build(ls(p), l, mid), build(rs(p), mid + 1, r);
        push_up(p);
    }
}
inline void cover_change(ll p, ll k){ 
    addtag[p] = 0, covertag[p] = k; 
    ans[p] = k;
}
inline void cover_down(ll p){
    if(covertag[p] != ctg_ex){
        ans[ls(p)] = ans[rs(p)] = covertag[p];
        covertag[ls(p)] = covertag[rs(p)] = covertag[p];
        addtag[ls(p)] = addtag[p] = 0;
        covertag[p] = ctg_ex;
    }
}
inline void add_change(ll p, ll k){
    cover_down(p);
    ans[p] += k, addtag[p] += k;
}
inline void add_down(ll p){
    if(addtag[p]){
        cover_down(p);
        ans[ls(p)] += addtag[p], ans[rs(p)] += addtag[p];
        addtag[ls(p)] += addtag[p], addtag[rs(p)] += addtag[p];
        addtag[p] = 0; 
    }
}
inline void push_down(ll p) { cover_down(p), add_down(p); }
inline void cover(ll c_l, ll c_r, ll p, ll l, ll r, ll k){
    if(c_l <= l && r <= c_r)
        cover_change(p, k);
    else{
        push_down(p);
        ll mid = l + r >> 1;
        if(c_l <= mid)
            cover(c_l, c_r, ls(p), l, mid, k);
        if(c_r > mid)
            cover(c_l, c_r, rs(p), mid + 1, r, k);
        push_up(p);
    }
}
inline void add(ll a_l, ll a_r, ll p, ll l, ll r, ll k){
    if(a_l <= l && r <= a_r){
        cover_down(p);
        ans[p] += k, addtag[p] += k;
    }
    else{
        push_down(p);
        ll mid = l + r >> 1;
        if(a_l <= mid)
            add(a_l, a_r, ls(p), l, mid, k);
        if(a_r > mid)
            add(a_l, a_r, rs(p), mid + 1, r, k);
        push_up(p);
    }
}
inline ll query(ll q_l, ll q_r, ll p, ll l, ll r){
    if(q_l <= l && r <= q_r)
        return ans[p];
    else{
        ll res = LONG_LONG_MIN;
        ll mid = l + r >> 1;
        if(q_l <= mid)
            res = max(res, query(q_l, q_r, ls(p), l, mid));
        if(q_r > mid)
            res = max(res, query(q_l, q_r, rs(p), mid + 1, r));
        return res;
    }
}
int main(){
    scanf("%lld%lld", &n, &q);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    while(q--){
        ll op, x, y, k;
        scanf("%lld%lld%lld", &op, &x, &y);
        if(op == 1){
            scanf("%lld", &k);
            cover(x, y, 1, 1, n, k);
        }else if(op == 2){
            scanf("%lld", &k);
            add(x, y, 1, 1, n, k);
        }else if(op == 3)
            printf("%lld\n", query(x, y, 1, 1, n));
    }
    return 0;
}

by Iniaugoty @ 2024-02-10 00:09:42

@qhj0906


|