萌新刚学OI,50pts WA求助

P1253 扶苏的问题

creation_hy @ 2022-11-01 17:17:44

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll INF = 4e18;
ll add[N << 2], chg[N << 2], ans[N << 2];
ll n, q;
inline ll read()
{
    ll s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = (s << 3) + (s << 1) + (ch ^ 48);
        ch = getchar();
    }
    return s * f;
}
inline int ls(int p)
{
    return p << 1;
}
inline int rs(int p)
{
    return p << 1 | 1;
}
inline void push_up(int p)
{
    ans[p] = max(ans[ls(p)], ans[rs(p)]);
}
inline void f(int p, int l, int r, ll k1, ll k2)
{
    if (k1)
    {
        add[p] += k1;
        ans[p] += k1;
    }
    if (k2 != INF)
    {
        ans[p] = chg[p] = k2;
        add[p] = 0;
    }
}
inline void push_down(int p, int l, int r)
{
    int mid = l + r >> 1;
    f(ls(p), l, mid, add[p], chg[p]);
    f(rs(p), mid + 1, r, add[p], chg[p]);
    add[p] = 0;
    chg[p] = INF;
}
inline void build(int p, int l, int r)
{
    add[p] = 0;
    chg[p] = INF;
    if (l == r)
    {
        ans[p] = read();
        return;
    }
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
inline void update(int p, int l, int r, int dl, int dr, ll k1, ll k2)
{
    if (dl <= l && r <= dr)
    {
        f(p, l, r, k1, k2);
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if (dl <= mid)
        update(ls(p), l, mid, dl, dr, k1, k2);
    if (mid < dr)
        update(rs(p), mid + 1, r, dl, dr, k1, k2);
    push_up(p);
}
inline ll query(int p, int l, int r, int qx, int qy)
{
    if (qx <= l && r <= qy)
        return ans[p];
    push_down(p, l, r);
    int mid = l + r >> 1;
    ll res = -INF;
    if (qx <= mid)
        res = max(res, query(ls(p), l, mid, qx, qy));
    if (mid < qy)
        res = max(res, query(rs(p), mid + 1, r, qx, qy));
    return res;
}
int main()
{
    /*ios::sync_with_stdio(false);
    cin.tie(nullptr);*/
    n = read();
    q = read();
    build(1, 1, n);
    ll op, l, r, k;
    while (q--)
    {
        op = read(), l = read(), r = read();
        switch (op)
        {
        case 1:
            k = read();
            update(1, 1, n, l, r, 0, k);
            break;
        case 2:
            k = read();
            update(1, 1, n, l, r, k, INF);
            break;
        default:
            printf("%d\n", query(1, 1, n, l, r));
        }
    }
    return 0;
}

|