关于珂朵莉树的区间推平
查看原帖
关于珂朵莉树的区间推平
728666
ZY_85楼主2023/10/12 13:16

在Split时,如果目标会在块中,则将块拆成左右两部分并返回右块

Code:
set<Node>::iterator split(int pos) {
    set<Node>::iterator it = s.lower_bound(Node(pos));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    if (it->r < pos) return s.end();
    ll l = it->l;
    ll r = it->r;
    ll v = it->v;
    s.erase(it);
    s.insert(Node(l, pos - 1, v));
    //insert函数返回pair,其中的first是新插入结点的迭代器
    return s.insert(Node(pos, r, v)).first;
}

而区间推平函数会直接调用Split(r+1)和Split(l)。

Code
void assign(ll l, ll r, ll x) {
    set<Node>::iterator itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(Node(l, r, x));
}

那么如果数据为:

[0,4]=2

[5,5]=3

请问调用assign(2,5,4)时,Split()中的右块构造并返回不会出错吗?


文中代码来自题解

2023/10/12 13:16
加载中...