前言
主要是一种暴力思想。。。
本文来自 wiki 与洛谷题解的整合。
应用
主要是应付随机数据（区间操作）
实现
有几个核心操作。
set实现方法
定义
struct node
{
intt l,r;//intt:long long
mutable intt v;
node(const intt &ll,const intt &rr,const intt &vv) : l(ll),r(rr),v(vv) {}
bool operator <(const node &o)const
{
return l<o.l;
}
};
set<node>odt;
split 操作（分裂）
auto split(int x)
{
auto it=odt.lower_bound(node(x,0,0));
if(it!=odt.end()&&it->l==x)return it;
it--;
intt l=it->l,r=it->r,v=it->v;
odt.insert(node(l,x-1,v));
return odt.insert(node(x,r,v)).first;
}
- 如果分裂的点恰好是某个区间的左端点，就不用分裂，保留即可。
- 如果分裂的点在一个区间的中间节点，就将其分为 \([l,x-1]\) 和 \([x,r]\) 这两个区间
- 注意：
odt.insert(node(x,r,v)).first这表示新加入的node的位置的迭代器（这是因为insert返回了一个pair，first就只新加入的node的位置的迭代器了）
assign 操作（区间推平）
void assign(intt l,intt r,intt v)//intt:long long
{
auto itr=split(r+1),itl=split(l);
odt.erase(itl,itr);
odt.insert(node(l,r,v));
}
将边角余料分裂出来，再将中间所有元素删除，最后加入推平区间。
如下图：
set的一个用法：erase(first,last)删除迭代器在 \([first,last)\) 范围内所有元素。