蒟蒻线段树60pts求调

P1253 扶苏的问题

Imken @ 2023-04-11 15:20:59

改了好几天了。。。真看不出来了

#include <iostream>
using namespace std;

long long dat[1000010];

template<typename type> inline void read(type& x)
{
    x = 0;
    bool flag(0);
    char ch = getchar();
    while (!isdigit(ch))
        flag = ch == '-', ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    flag ? x = -x : 0;
}

template<typename type> inline void write(type x, bool mode = 1)
{
    x < 0 ? x = -x, putchar('-') : 0;
    static short Stack[50], top(0);
    do
        Stack[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        putchar(Stack[top--] | 48);
    mode ? putchar('\n') : putchar(' ');
}

class SegmentFaultTree {
private:
    const long long NaN = 0;
    const long long NOT_FOUND = (-1e18 + 114514);

    struct Node {
        int l, r;
        long long lz, val;
        long long set = (-1e18 + 114514);
    } node[4000010];

    void update_lazy(int p, long long lz) { node[p].lz += lz; node[p].val += lz; }

    void upd_overwrite_lazy(int p, long long set)
    {
        node[p].lz = 0; 
        node[p].val = node[p].set = set;
    }

    void pushdown(int p)
    {
        if (node[p].set != NOT_FOUND) {
            // node[p].val = node[p].set;
            upd_overwrite_lazy(p << 1, node[p].set);
            upd_overwrite_lazy((p << 1) + 1, node[p].set);
            node[p].set = NOT_FOUND;
        } else {
            update_lazy(p << 1, node[p].lz);
            update_lazy((p << 1) + 1, node[p].lz);
        }
        node[p].set = NOT_FOUND;
        node[p].lz = 0;
    }
public:
    SegmentFaultTree() {}

    void build(int l, int r, int p = 1)
    {
        node[p].l = l;
        node[p].r = r;
        if (l == r) {
            node[p].val = dat[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, p << 1);
        build(mid + 1, r, (p << 1) + 1);
        node[p].val = max(node[(p << 1)].val, node[(p << 1) + 1].val);
    }

    // Add
    void update_nodes(int l, int r, long long val, int p = 1)
    {
        if (node[p].l > r || node[p].r < l) return;
        if (node[p].l >= l && node[p].r <= r) {
//          update_lazy(p, val);
            node[p].lz += val;
            node[p].val += val;
            return;
        }
        pushdown(p);
        update_nodes(l, r, val, (p << 1));
        update_nodes(l, r, val, (p << 1) + 1);
        node[p].val = max(node[(p << 1)].val, node[(p << 1) + 1].val);
    }

    // Overwrite
    void overwrite_nodes(int l, int r, long long val, int p = 1)
    {
        if (node[p].l > r || node[p].r < l) return;
        if (node[p].l >= l && node[p].r <= r) {
            upd_overwrite_lazy(p, val);
            return;
        }
        pushdown(p);
        overwrite_nodes(l, r, val, (p << 1));
        overwrite_nodes(l, r, val, (p << 1) + 1);
        node[p].val = max(node[(p << 1)].val, node[(p << 1) + 1].val);
    }

    long long query(int l, int r, int p = 1)
    {
        if (node[p].l > r || node[p].r < l) return NOT_FOUND;
        if (node[p].l >= l && node[p].r <= r) return node[p].val;
        pushdown(p);
        return max(query(l, r, (p << 1)), query(l, r, (p << 1) + 1));
    }
};

SegmentFaultTree tree;

int n, m, tp;
int opt;
int x, y;
long long z;

signed main()
{
    read(n), read(m);
    for (int i = 1; i <= n; i++) {
        read(dat[i]);
    }
    tree.build(1, n);
    while (m--) {
        read(opt), read(x), read(y);
        switch (opt) {
            case 1:
                read(z);
                tree.overwrite_nodes(x, y, z);
                break;
            case 2:
                read(z);
                tree.update_nodes(x, y, z);
                break;
            case 3:
                write(tree.query(x, y));
                break;
            default: break;
        }
    }
    return 0;
}

WA on #6~#10


by Imken @ 2023-04-11 16:47:52

@comcopy OK 万分感谢qwq


上一页 |