在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));
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()中的右块构造并返回不会出错吗?
文中代码来自题解