【模板】ODT | Old Driver Tree | 珂朵莉树

posted on 2021-04-02 20:38:49 | under 学术 | source

这个东西本身不常用，但是这个维护连续段的写法很常用。

标签：暴力、数据结构、std::set

#include <set>
template<class T=long long>
class ODT{
    private:
        struct node{
            int l,r;
            mutable T v;
            node(int l,int r=-1,T v=0):l(l),r(r),v(v){}
            inline bool operator<(const node &b)const{return l<b.l;}
            inline friend int rangelen(const node &a){return a.r-a.l+1;}
        };
        std::set<node> s;
        typedef typename std::set<node>::iterator IT;
    public:
        void init(int n,int *a){
            s.insert(node(n+1,n+1));
            for(int i=1;i<=n;i++) s.insert(node(i,i,a[i]));
        }
        IT split(int pos){
            IT it=s.lower_bound(node(pos));
            if(it!=s.end()&&it->l==pos) return it;
            --it;
            int l=it->l,r=it->r;
            T v=it->v;
            s.erase(it);
            s.insert(node(l,pos-1,v));
            return s.insert(node(pos,r,v)).first;
        }
        void assign(int l,int r,T v=0){
            IT R=split(r+1),L=split(l);
            s.erase(L,R);
            s.insert(node(l,r,v));
        }
//        template<class function>
//        void work(int l,int r,function work){
//            IT R=split(r+1),L=split(l);
//            for(IT it=L;it!=R;++it) work();
//        }
};