一个(仿佛)和C++版本有关的问题

P3391 【模板】文艺平衡树

lkrkerry @ 2024-05-28 20:13:16

该题目用C++17提交可以AC,但使用C++14提交会WA+RE

#include <vector>
#include <iostream>
#define int long long

using namespace std;

int n, m;
struct Node
{
    int fa, ch[2], val, sz;
    bool lazy;
    Node(int val = 0, int fa = 0, int l = 0, int r = 0, int sz = 0, bool lazy = false)
        : val(val), fa(fa), sz(sz), lazy(lazy)
    {
        ch[0] = l;
        ch[1] = r;
    }
};

struct SplayTree
{
    vector<Node> tree;
    int rt;
    SplayTree()
    {
        tree.push_back(Node());
        rt = 0;
    }
    int build(int l, int r, int f, vector<int> &a)
    {
        if (l > r)
            return 0;
        int mid = (l + r) / 2;
        tree.push_back(Node(a[mid], f));
        int cur = tree.size() - 1;
        tree[cur].ch[0] = build(l, mid - 1, cur, a);
        tree[cur].ch[1] = build(mid + 1, r, cur, a);
        maintain(cur);
        cout << cur << endl;
        return rt = cur;
    }
    void maintain(int x)
    {
        tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz + 1;
    }
    bool get(int x)
    {
        return x == tree[tree[x].fa].ch[1];
    }
    void revlazy(int x)
    {
        swap(tree[x].ch[0], tree[x].ch[1]);
        tree[x].lazy ^= 1;
    }
    void push_down(int x)
    {
        if (tree[x].lazy)
        {
            revlazy(tree[x].ch[0]);
            revlazy(tree[x].ch[1]);
            tree[x].lazy = 0;
        }
    }
    void rotate(int x)
    {
        // rotate in dir automaticaly
        int y = tree[x].fa, z = tree[y].fa, chk = get(x);
        tree[y].ch[chk] = tree[x].ch[chk ^ 1];
        if (tree[x].ch[chk ^ 1])
        {
            tree[tree[x].ch[chk ^ 1]].fa = y;
        }
        tree[x].ch[chk ^ 1] = y;
        tree[y].fa = x;
        tree[x].fa = z;
        if (z)
            tree[z].ch[y == tree[z].ch[1]] = x;
        maintain(y);
        maintain(x);
    }
    void splay(int x, int goal = 0)
    {
        if (goal == 0)
            rt = x;
        while (tree[x].fa != goal)
        {
            int f = tree[x].fa, g = tree[f].fa;
            if (g != goal)
            {
                if (get(f) == get(x)) // same turn
                    rotate(f);
                else
                    rotate(x);
            }
            rotate(x);
        }
    }
    int kth(int k)
    {
        int cur = rt;
        while (1)
        {
            cout << tree[cur].val << " " << k << endl;
            system("pause");
            push_down(cur);
            if (tree[cur].ch[0] && k <= tree[tree[cur].ch[0]].sz)
            {
                cur = tree[cur].ch[0];
            }
            else
            {
                // minus rank from left tree
                k -= (1 + tree[tree[cur].ch[0]].sz);
                if (k <= 0)
                {
                    splay(cur);
                    return cur;
                }
                cur = tree[cur].ch[1];
            }
        }
    }
    void reverse(int l, int r)
    {
        int l2 = kth(l), r2 = kth(r + 2); // remember to - and +
        splay(l2);
        splay(r2, l2);                        // make l,r together to swap
        int tmp = tree[tree[l2].ch[1]].ch[0]; // ch 1 is r2, ch 1 ch 0 is used
        revlazy(tmp);
    }
    void print(int x)
    {
        push_down(x);
        if (tree[x].ch[0])
            print(tree[x].ch[0]);
        if (tree[x].val >= 1 && tree[x].val <= n)
            cout << tree[x].val << " ";
        if (tree[x].ch[1])
            print(tree[x].ch[1]);
    }
};

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    auto tree = SplayTree();
    auto a = vector<int>(n + 2);
    for (int i = 1; i <= n + 1; i++)
    {
        a[i] = i;
    }
    int rt = tree.build(0, n + 1, 0, a);
    for(int i=0;i<=n+1;i++){
        cout << tree.tree[i].val << " " << tree.tree[i].sz << endl;
    }
    cout << endl;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        tree.reverse(l, r);
    }
    tree.print(tree.rt);
    cout << endl;
    return 0;
}
  • 通过:https://www.luogu.com.cn/record/159997139
  • 失败: https://www.luogu.com.cn/record/159997035

by cmk666 @ 2024-05-28 20:39:06

在函数 build 里:

...
tree.push_back(...);
...
tree[...] = build(...);
...

在调用 build 的时候,会给 tree 这个 vector 进行 push_back,可能会导致扩容,致使迭代器、引用失效。在 C++14 及以前,tree[...] = build(...) 这一句的行为可能是:

  1. tree[...] 的引用;
  2. 调用 build(...)
  3. 把值赋值给引用(此时引用可能因为扩容而失效,导致 UB)。

C++17 及以后,标准规定了 = 是先算右边再算左边,即上述过程的 1,2 swap 一下,于是不会出现引用失效的问题。


by lkrkerry @ 2024-05-29 11:21:48

谢谢,关注了


|