蒟蒻线段树60pts求调

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;
}

by Imken @ 2023-04-11 15:22:49

更正：WA on #7~#10

by Caiest_Oier @ 2023-04-11 16:00:06

@immccn123 lazy标记的写法好像有点错误

by Imken @ 2023-04-11 16:09:11

@Caiest_Oier 我知道是lazy 但是改了很多版都不对

by Caiest_Oier @ 2023-04-11 16:15:22

@immccn123 要我给你写一版吗

by Imken @ 2023-04-11 16:16:01

@Caiest_Oier 主要还是看不出来lazy那里有什么问题啥的

by Imken @ 2023-04-11 16:23:12

@Caiest_Oier

要我给你写一版吗

行

by comcopy @ 2023-04-11 16:35:52

艹，等我一起找出来再说吧(

by comcopy @ 2023-04-11 16:41:38

@immccn123 OK你是先覆盖后加的，那么你覆盖和加不应该用else，把下传标记时的else删了就过了

by comcopy @ 2023-04-11 16:41:55

看到else还以为你是先加后覆盖的(

by comcopy @ 2023-04-11 16:42:11

#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;
            }
            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;
}