RT,确定是珂朵莉树的问题,在某些操作之后 set 里的元素会出现诸如 r>l,两个区间有交集/包含等等奇怪的现象。
但是我调不出来了/kk
template<typename T>
struct Node{
int l,r;
mutable T v;
Node(int _l=1,int _r=n,T _v=T()):l(_l),r(_r),v(_v){}
~Node(){}
bool operator <(const Node &x)const{return l<x.l;}
};
template<typename T>
class ODT{
private:
set<Node<T>>s;
void _Insert(int l,int r,T v){s.emplace(l,r,v);}
auto _Split(int x){
if(x>n)return s.end();
auto it=s.lower_bound(Node<T>(x,0,T()))--;
if(it->l==x)return it;
int l=it->l,r=it->r;T v=it->v;
s.erase(it);
s.emplace(l,x-1,v);
return s.emplace(x,r,v).first;
}
void _Assign(int l,int r,T v){
auto pr=_Split(r+1),pl=_Split(l);
s.erase(pl,pr);
s.emplace(l,r,v);
}
template<typename _For_Init,typename _For_Iterator,typename _For_Interval>
auto _Performance(
int l,int r,
_For_Init _Func_For_Init,
_For_Iterator _Func_For_Iterator,
_For_Interval _Func_For_Interval){
auto pr=_Split(r+1),pl=_Split(l);
_Func_For_Init();
for(auto it=pl;it!=pr;it++)_Func_For_Iterator(it);
return _Func_For_Interval();
}
......