一个神奇的问题，求助

P2572 [SCOI2010] 序列操作

日居月诸 @ 2020-10-27 10:40:47

这道题，我这样用结构体写是对的

struct Node {
    int sum, len, tag;
    int val1, lv1, rv1;
    int val0, lv0, rv0;
    void merge(Node a, Node b) {
        sum = a.sum + b.sum;

        if(a.val1 == a.len) lv1 = a.len + b.lv1;
        else lv1 = a.lv1;
        if(a.val0 == a.len) lv0 = a.len + b.lv0;
        else lv0 = a.lv0;

        if(b.val1 == b.len) rv1 = b.len + a.rv1;
        else rv1 = b.rv1;
        if(b.val0 == b.len) rv0 = b.len + a.rv0;
        else rv0 = b.rv0;

        val1 = max(max(a.val1, b.val1), a.rv1 + b.lv1);
        val0 = max(max(a.val0, b.val0), a.rv0 + b.lv0);
    }
}t[MAXN << 2];
//...

t[o].merge(t[ls], t[rs]);//调用

但是如果这样写，就会出现神奇的答案：

struct Segment_tree {
    struct Node {
        int sum, len, tag;
        int val1, lv1, rv1;
        int val0, lv0, rv0;
    }t[MAXN << 2];
    Node merge(Node a, Node b) {
        Node res;

        res.sum = a.sum + b.sum;

        if(a.val1 == a.len) res.lv1 = a.len + b.lv1;
        else res.lv1 = a.lv1;
        if(a.val0 == a.len) res.lv0 = a.len + b.lv0;
        else res.lv0 = a.lv0;

        if(b.val1 == b.len) res.rv1 = b.len + a.rv1;
        else res.rv1 = b.rv1;
        if(b.val0 == b.len) res.rv0 = b.len + a.rv0;
        else res.rv0 = b.rv0;

        res.val1 = max(max(a.val1, b.val1), a.rv1 + b.lv1);
        res.val0 = max(max(a.val0, b.val0), a.rv0 + b.lv0);

        return res;
    }
//...

t[o] = merge(t[ls], t[rs]);//调用

追踪输出发现，有些节点的sum值是随机数。这个是什么问题呢？求dalao赐教

by 日居月诸 @ 2020-10-27 10:45:11

哦对了第一种方法里我有个地方使用了

Node query(int o, int l, int r, int x, int y) {
        if(x <= l && r <= y) return t[o];
        pushdown(o);
        int m = (l + r) >> 1;
        if(y <= m) return query(ls, l, m, x, y);
        else if(x > m) return query(rs, m+1, r, x, y);
        else {
            Node ans; ans.merge(query(ls, l, m, x, y), query(rs, m+1, r, x, y));
            return ans;
        }
    }

而第二种方法用的是

Node query(int o, int l, int r, int x, int y) {
        if(x <= l && r <= y) return t[o];
        pushdown(o);
        int m = (l + r) >> 1;
        if(y <= m) return query(ls, l, m, x, y);
        else if(x > m) return query(rs, m+1, r, x, y);
        return merge(query(ls, l, m, x, y), query(rs, m+1, r, x, y));
    }

不知道这有没有什么问题？

by 日居月诸 @ 2020-10-27 10:49:20

是因为C++一些什么内存释放的特性吗

by TinyMirror1 @ 2020-10-27 10:50:56

@日居月诸

我之前也遇到过这种类似的问题

你的第二种更新新建了一个res，但是仔细看你的代码 res.len 和 res.tag你给漏掉了，并没有更新，变成随机数了，所以你以的区间就错了

第二种更新一定要把所有元素都更新，否则就会变成随机

第一种的话其他数据是不会变的所以不会出错

by 日居月诸 @ 2020-10-27 10:56:10

@Tiny_Mirror

也就是由于我在上传的时候，len没有及时存储下来，然后t[o] = merge(t[ls], t[rs]);就出错了的意思把。

谢谢大佬！