50pts玄关求调

P1253 扶苏的问题

ln001 @ 2024-02-17 16:54:19

记录

#include <bits/stdc++.h>
#define ll long long
#define fst                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define f(x, y, z) for (register ll x = (y); (z >= y) ? (x <= (z)) : (x >= (z)); x += ((z >= y) ? 1 : -1))
using namespace std;
ll read_tmp = INT_MAX;
inline ll read(ll &k = read_tmp);
const long long INF = 0x3f3f3f3f3f3f3f3f, N = 1e6 + 10;
ll n = read(), a[N], q = read();
namespace segment_tree
{
#define ls(x) ((x) << 1)     //左节点
#define rs(x) ((x) << 1 | 1) //右节点
#define fa(x) ((x) >> 1)     //父节点
struct node
{
    ll l, r, sum, add_tag;
    ll maxx, fg;
    bool has_fg = 0;
};

node t[4 * N];

inline void push_up(ll p)
{
    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
    t[p].maxx = max(t[ls(p)].maxx, t[rs(p)].maxx);
    return;
}

inline void build(ll l = 1, ll r = N, ll p = 1)
{
    t[p].l = l;
    t[p].r = r;
    if (l == r)
    {
        t[p].sum = a[l];
        t[p].maxx = a[l];
        return;
    }
    ll mid = l + r >> 1;
    build(l, mid, ls(p));
    build(mid + 1, r, rs(p));
    push_up(p);
    return;
}

inline void lazy_tag(ll p, ll mul, ll add)
{
    t[p].sum = t[p].sum + add * (t[p].r - t[p].l + 1);
    t[p].maxx += add;
    t[p].add_tag = t[p].add_tag + add;
    return;
}
inline void fg_lazy_tag(ll p, ll x)
{

    t[p].sum = x * (t[p].r - t[p].l + 1);
    t[p].maxx = x;
    t[p].fg = x;
    t[p].has_fg = 1;
    t[p].add_tag = 0;
    return;
}
inline void push_down(ll p)
{
    if (t[p].has_fg)
    {
        fg_lazy_tag(ls(p), t[p].fg);
        fg_lazy_tag(rs(p), t[p].fg);
    }
    lazy_tag(ls(p), 1, t[p].add_tag);
    lazy_tag(rs(p), 1, t[p].add_tag);
    t[p].add_tag = 0;
    t[p].has_fg = 0;
    return;
}

inline void update(ll l, ll r, ll p, ll mul = 1, ll add = 0)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        lazy_tag(p, mul, add);
        return;
    }
    push_down(p);
    ll mid = t[p].l + t[p].r >> 1;
    if (l <= mid)
        update(l, r, ls(p), mul, add);
    if (r > mid)
        update(l, r, rs(p), mul, add);
    push_up(p);
    return;
}

inline ll query(ll l, ll r, ll p = 1)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        return t[p].sum;
    }
    push_down(p);
    ll mid = t[p].l + t[p].r >> 1, sum = 0;
    if (l <= mid)
        sum = sum + query(l, r, ls(p));
    if (r > mid)
        sum = sum + query(l, r, rs(p));
    return sum;
}
inline ll check_max(ll l, ll r, ll p = 1)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        return t[p].maxx;
    }
    push_down(p);
    ll mid = t[p].l + t[p].r >> 1, maxx = 0;
    if (l <= mid)
        maxx = max(maxx, check_max(l, r, ls(p)));
    if (r > mid)
        maxx = max(maxx, check_max(l, r, rs(p)));
    return maxx;
}

inline void set_fg(ll l, ll r, ll p, ll x)
{
    if (l <= t[p].l && t[p].r <= r)
    {
        fg_lazy_tag(p, x);
        return;
    }
    push_down(p);
    ll mid = t[p].l + t[p].r >> 1;
    if (l <= mid)
        set_fg(l, r, ls(p), x);
    if (r > mid)
        set_fg(l, r, rs(p), x);
    push_up(p);
    return;
}
#undef ls(x)
#undef rs(x)
#undef fa(x)
} // namespace segment_tree
using namespace segment_tree;
signed main()
{
    f(i, 1, n) read(a[i]);
    build(1, n, 1);
    f(i, 1, q)
    {
        ll op = read(), l, r, x;
        if (op == 1) //推为x
        {
            l = read();
            r = read();
            x = read();
            set_fg(l, r, 1, x);
        }
        if (op == 2)
        {
            l = read();
            r = read();
            x = read();
            update(l, r, 1, 1, x);
        }
        if (op == 3) //查最大
        {
            l = read();
            r = read();
            cout << check_max(l, r, 1) << endl;
        }
        goto debug;
        if (op == 4) //debug
        {
            cin >> l >> r;
            cout << query(l, r) << endl;
        }
    debug:;
    }
    return 0;
}

inline ll read(ll &k)
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    if (k != INT_MAX)
        return k = x * f;
    return x * f;
}

by 杜都督 @ 2024-02-17 17:12:08

修改check_max()中ll maxx = -INF;即可AC


|