珂朵莉树求调
  • 板块学术版
  • 楼主Ew_Cors
  • 当前回复26
  • 已保存回复26
  • 发布时间2022/8/27 10:49
  • 上次更新2023/10/27 13:29:41
查看原帖
珂朵莉树求调
180103
Ew_Cors楼主2022/8/27 10:49

RT,确定是珂朵莉树的问题,在某些操作之后 set 里的元素会出现诸如 r>lr>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();
    }
......
2022/8/27 10:49
加载中...