90分,但是第十个点WA!!!!(不是TLE)

P1253 扶苏的问题

Swiftie_wyc22 @ 2022-08-12 19:10:56

#include <bits/stdc++.h>
#define LL long long
#define QWQ -1145141919810
using namespace std;
LL n, q;
struct Tree
{
    int left, right;
    LL max;
    LL coverDelta;
    LL addDelta;
};
Tree tree[4 * 5000000 + 10];
LL a[500010];
#define ls id<<1
#define rs id<<1|1
void build(LL id, LL l, LL r)
{
    tree[id].left = l;
    tree[id].right = r;
    // tree[id].max = LLONG_MIN;
    if (l == r)
    {
        tree[id].coverDelta = QWQ;
        tree[id].max = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    tree[id].max = max(tree[id * 2].max, tree[id * 2 + 1].max);

}
inline void coverpushdown(LL id)
{
    if (tree[id].coverDelta != QWQ)
    {
        tree[ls].addDelta = tree[rs].addDelta = 0;
        tree[ls].max = tree[rs].max = tree[id].coverDelta;
        tree[ls].coverDelta = tree[rs].coverDelta = tree[id].coverDelta;
        tree[id].coverDelta = QWQ;
    }
}
inline void addpushdown(LL id)
{
    if (tree[id].addDelta)
    {
        coverpushdown(id);
        tree[ls].max += tree[id].addDelta;
        tree[rs].max += tree[id].addDelta;
        tree[ls].addDelta +=tree[id].addDelta;
        tree[rs].addDelta += tree[id].addDelta;
        tree[id].addDelta = 0;
    }
}

inline void pushdown(LL id)
{
    coverpushdown(id);
    addpushdown(id);
}
inline void change(LL id, LL l, LL r, LL val)
{
    if (tree[id].left > r || tree[id].right < l)
        return;
    if (tree[id].left >= l && tree[id].right <= r)
    {
        tree[id].addDelta = 0;
        tree[id].max = val;
        tree[id].coverDelta = val;
        return;
    }
    pushdown(id);
    change(ls, l, r, val);
    change(rs, l, r, val);
    tree[id].max = max(tree[ls].max, tree[rs].max);
}

inline void update(LL id, LL l, LL r, LL delta)
{
    if (tree[id].left > r || tree[id].right < l)
        return;
    //  if (tree[id].left == tree[id].right)
    //      tree[id].max += delta;
    if (tree[id].left >= l && tree[id].right <= r)
    {
        coverpushdown(id);
        tree[id].max += delta;
        tree[id].addDelta += delta;
        return;
    }
    pushdown(id);

    update(2 * id, l, r, delta);
    update(2 * id + 1, l, r, delta);
    tree[id].max = max(tree[ls].max, tree[rs].max);
}

inline LL query(LL id, LL l, LL r)
{
    if (tree[id].left > r || tree[id].right < l)
        return LLONG_MIN;
    if (tree[id].left >= l && tree[id].right <= r)
    {
        return tree[id].max;
    }
    pushdown(id);

        return max(query(2 * id, l, r), query(2 * id + 1, l, r));
}
/*
void print_tree(int id)
{
    if (tree[id].left == tree[id].right)
    {
        printf("id = %lld, max = %lld, tree[id].left = %lld, tree[id].right = %lld \n", id, tree[id].max, tree[id].left, tree[id].right);
        //      cout << tree[id].max << " ";
        return;
    }
    printf("id = %lld, max = %lld, tree[id].left = %lld, tree[id].right = %lld \n", id, tree[id].max, tree[id].left, tree[id].right);
    print_tree(id * 2);
    print_tree(id * 2 + 1);
}*/

int main()
{
    ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    build(1, 1, n);
    //  print_tree(1);
    for (int i = 1; i <= n * 4+100; i++)
        tree[i].coverDelta = QWQ;

    LL op, x, l, r;
    while (q--)
    {
        cin >> op;
        if (op == 1)
        {
            cin >> l >> r >> x;
            change(1, l, r, x);
            //          print_tree(1);cout << endl;
        }
        else if (op == 2)
        {
            cin >> l >> r >> x;
            update(1, l, r, x);
            //          print_tree(1);cout << endl;
        }
        else
        {
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}

by 大眼仔Happy @ 2022-08-12 19:29:56

@Swiftie_wyc22 有这么长吗,看你写出了200行的气势......


by Swiftie_wyc22 @ 2022-08-12 19:46:36

@大眼仔Happy 我我我……额,我我,会的只有这个…………


by P32sx @ 2022-10-16 19:42:14

数组开小


|