动态开点线段树玄学问题求解

P3372 【模板】线段树 1

bsdsdb @ 2024-06-21 12:48:31

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll MAXN = 1e5, MAXV = 1e5;

struct sec {
    ll id, val, l, r, len;
    sec(ll i, ll v, ll lf, ll rg, ll ln) {
        id = i;
        val = v;
        l = lf;
        r = rg;
        len = ln;
    }
    sec() {
        id = val = l = r = len = 0;
    }
};
struct opr {
    ll val;
    opr(ll v) {
        val = v;
    }
    opr() {
        val = 0;
    }
};
sec com(sec x, sec y, ll i) {
    return sec(i, x.val + y.val, x.id, y.id, x.len + y.len);
}
sec com(sec x, opr y) {
    return sec(x.id, x.val + y.val * x.len, x.l, x.r, x.len);
}
opr com(opr x, opr y) {
    return opr(x.val + y.val);
}
sec com(sec x, ll y) {
    return com(x, opr(y));
}
opr com(opr x, ll y) {
    return com(x, opr(y));
}
struct segTree {
    ll size, rt;
    vector<sec> val;
    vector<opr> tag;
    void pushdown(ll x) {
        tag[val[x].l] = com(tag[val[x].l], tag[x]);
        val[val[x].l] = com(val[val[x].l], tag[x]);
        tag[val[x].r] = com(tag[val[x].r], tag[x]);
        val[val[x].r] = com(val[val[x].r], tag[x]);
        tag[x] = tag[0] = opr();
        val[0] = sec();
    }
    void pushup(ll x) {
        val[x] = com(val[val[x].l], val[val[x].r], x);
    }
    segTree() {
        val.push_back(sec());
        val.push_back(sec(1, 0, 0, 0, MAXV));
        tag.push_back(opr());
        tag.push_back(opr());
        size = MAXV;
        rt = 1;
    }
    ll mdf(ll x, ll lx, ll rx, ll l, ll r, ll k) {
        if (x == 0) {
            x = val.size();
            val.push_back(sec(x, 0, 0, 0, rx - lx));
            tag.push_back(opr());
        }
        if (r <= lx || rx <= l) {
            return x;
        }
        if (l <= lx && rx <= r) {
            tag[x] = com(tag[x], k);
            val[x] = com(val[x], k);
            return x;
        }
        pushdown(x);
        ll mid = (lx + rx) / 2;
        ll lc = mdf(val[x].l, lx, mid, l, r, k);
        val[x].l = lc;
        ll rc = mdf(val[x].r, mid, rx, l, r, k);
        val[x].r = rc;
        pushup(x);
        return x;
    }
    ll qry(ll x, ll lx, ll rx, ll l, ll r) {
        if (x == 0) {
            return sec().val;
        }
        if (r <= lx || rx <= l) {
            return sec().val;
        }
        if (l <= lx && rx <= r) {
            return val[x].val;
        }
        pushdown(x);
        ll mid = (lx + rx) / 2;
        return qry(val[x].l, lx, mid, l, r) + qry(val[x].r, mid, rx, l, r);
    }
    void out(ll x, ll lx, ll rx) {
        if (x == 0) {
            return;
        }
        cout << "val[" << x << "[" << lx << "," << rx - 1 << "]]=" << val[x].val << " " << val[x].l << " " << val[x].r << " " << val[x].len << endl;
        cout << "tag[" << x << "[" << lx << "," << rx - 1 << "]]=" << tag[x].val << endl;
        ll mid = (lx + rx) / 2;
        out(val[x].l, lx, mid);
        out(val[x].r, mid, rx);
    }
} st;

ll n, q;

int main() {
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        ll v;
        cin >> v;
        st.mdf(st.rt, 1, st.size + 1, i, i + 1, v);
    }
    while (q--) {
        ll o, l, r, k;
        cin >> o >> l >> r;
        if (o == 1) {
            cin >> k;
            st.mdf(st.rt, 1, st.size + 1, l, r + 1, k);
        } else {
            cout << st.qry(st.rt, 1, st.size + 1, l, r + 1) << endl;
        }
    }
    return 0;
}

可以AC，但是如果将代码中的

ll lc = mdf(val[x].l, lx, mid, l, r, k);
val[x].l = lc;
ll rc = mdf(val[x].r, mid, rx, l, r, k);
val[x].r = rc;

换成

val[x].l = mdf(val[x].l, lx, mid, l, r, k);
val[x].r = mdf(val[x].r, mid, rx, l, r, k);

就会7WA3RE（但是mac上下载数据测试能AC，洛谷就不行），调试发现有时候子树编号会被赋值为0，即使mdf返回的值是正确的

如果把mdf中的x换成引用：

ll mdf(ll& x, ll lx, ll rx, ll l, ll r, ll k) {
    if (x == 0) {
        x = val.size();
        val.push_back(sec(x, 0, 0, 0, rx - lx));
        tag.push_back(opr());
    }
    if (r <= lx || rx <= l) {
        return x;
    }
    if (l <= lx && rx <= r) {
        tag[x] = com(tag[x], k);
        val[x] = com(val[x], k);
        return x;
    }
    pushdown(x);
    ll mid = (lx + rx) / 2;
    mdf(val[x].l, lx, mid, l, r, k);
    mdf(val[x].r, mid, rx, l, r, k);
    pushup(x);
    return x;
}

就是1WA3RE，调试后发现在val push_back之后上层递归中的x会莫名其妙地变成0

why?

by bsdsdb @ 2024-06-21 12:50:16

1 2 3

by Z_301 @ 2024-06-21 14:39:52

@0x28202e202e29 vector 的 push_back 导致的。具体可以看这里的「迭代器失效」那一栏。

省流：push_back 在 vector 容量满了以后会重新分配内存，即新 new 一块然后把数据拷贝上去，这会导致原来的引用失效。

by bsdsdb @ 2024-06-21 18:43:36

@Z_301 谢谢。那第二个mdf返回值的问题呢

by Z_301 @ 2024-06-21 19:01:58

@0x28202e202e29 一样啊，因为 val[x]=func() 语句会先取出 val[x] 的引用，再执行 func() 。

可以运行以下程序来验证上述规则：

#include<bits/stdc++.h>
using namespace std;
int a[10],t;
struct A {
    int& operator[](int k) {
        cerr<<t<<endl;
        return a[t+k];
    }
}b;
int func() {
    return t=1;
}
int main() {
    b[0]=func();
}
// output: 1

by bsdsdb @ 2024-06-21 19:48:03

@Z_301 没太懂，函数运行完后不会返回一个值，然后运行赋值操作将返回值赋给左边吗，为什么例子中mdf的return x返回一个正确的值，在运行val[x].l=mdf()的时候val[x].l接收到的却是0呢

by bsdsdb @ 2024-06-21 19:55:40

https://www.luogu.com.cn/problem/solution/P3919 的第一篇的maketree部分好像也是类似的写法，但是没问题

int maketree(int node,int begin,int end){
    node=++top;
    if(begin==end){
        tree[node].val=a[begin];
        return top;
    }
    int mid=(begin+end)>>1;
    tree[node].l=maketree(tree[node].l,begin,mid);
    tree[node].r=maketree(tree[node].r,mid+1,end);
    return node;
}

by Z_301 @ 2024-06-21 20:02:59

@0x28202e202e29

首先请确保你懂「operator」和「引用」的概念（如果不懂就去百度）。

val[x] 的本质是 val.operator[](x) ，即调用一个函数，返回值是一个引用。如果 val 发生了扩容，那么这个引用就会失效，从而导致一系列问题。

我上面那段回复的意思是，如果执行 val[x].l=mdf() ，那么会先调用 val[x] 也就是 val.operator[](x) ，来得到一个引用，然后再调用 mdf() 。

这样带来的后果是，如果你在 mdf() 中应用了一些操作（如 push_back ），使得 val 扩容了，从而导致赋值失败，呈现出的结果就是 val[x].l 还是 0。

by Z_301 @ 2024-06-21 20:04:19

@0x28202e202e29 那个没问题是因为他用的数组，而你用的 vector ，这是主要区别。

（也就是说只要你也用数组就没这么多事了）

by bsdsdb @ 2024-06-21 20:15:32

@Z_301 谢谢。