我可爱的珂朵莉树

珂朵莉树又名 $ODT (Old \ Driver \ Tree)$
在数据随机的情况下极其优秀，会有些意想不到的结果
思维简单暴力，操作简单粗暴

$1.$ 实现原理

就是现对于原数组 $A$ 相同颜色段推平然后一起处理。必然如果数据部随机一种颜色一格一定会有非常美妙的效果。

$2.$ 实现方式

$2.1$ 初始化

我们可以用一个三元组 $(l,r,v)$ 分别表示被推平后 $($ 用 $set$ 来维护即可 $)$ 的左右端点以及区间值。

代码如下：

vector<pair<int,int> >g;
struct nood {
    int l,r;
    mutable int v;
    inline bool friend operator < (const nood &a,const nood &b) {
        return a.l<b.l;
    }
};
set<nood> S;
typedef set<nood>::iterator It;

$2.2$ $ODT$ 的两个重要操作 $split/assign$

对于 $split$ 操作的原理就是把 $[l,r]$ 这段区间分成 $[l,pos],[pos,r]$ 两端区间，返回 $[pos,r]$ 的迭代器。直接用 $lower\ bound$ 二分找出 $pos$ 所在区间即可。

加上一个小特判：如果不需要 $split$ 就直接返回

if(it!=S.end()&&it->l==pos) return it;

具体代码如下：

inline It split(int pos) {
    It it=S.lower_bound((nood){pos,-1,0});  //二分找到pos所在区间 
    if(it!=S.end()&&it->l==pos) return it;  //小特判
    it--; //如果这段区间找不到，退一个区间
    int ll=it->l;
    int rr=it->r;
    int val=it->v;
    S.erase(it); //删除原先的
    S.insert((nood){ll,pos-1,val});
    return S.insert((nood){pos,rr,val}).first; //加入新增的
}

对于 $assign$ 操作（珂朵莉树的推平操作）

这种操作就是先把区间 $[l,r]$ 的值变为 $val$ ,再把这个区间推平变成 $ODT$ 上的一个点。关键在于由于大部分题目数据随机所以 $ODT$ 上的点会快速减少所以 $ODT$ 此时的复杂度接近 $O(m\log n)$

代码如下：

inline void assign(const int &l,const int &r,const int &v) {
    It R=split(r+1),L=split(l);
    S.erase(L,R);
    S.insert((nood){l,r,v});
}

$2.3$ $ODT$ 其他更加简单暴力的操作，这边举几个例子：

$(a)$ 区间加

inline void add(int l,int r,int val) {
    It L=split(l),R=split(r+1);
    for ( It it=L;it!=R;it++ ) (it->v)+=val;
}

$(b)$ 区间求和

inline int query(int l,int r) {
    It R=split(r+1),L=split(l);
    int ret=0;
    for ( It it=L;it!=R;it++ ) 
        ret+=(it->v)*(it->r-it->l+1); //注意这边是(it->r-it->l+1)一开始就搞错了（其实这个点代表着一个区间）
    return ret;
}

$(c)$ 区间覆盖

就是把 $[l,r]$ 这段区间覆盖到 $[ll,rr]$ 上面去

这是我们有个简单粗暴的方法就是先记个桶先把 $[l,r]$ 区间里的信息记到桶里去再用这个桶的信息去修改 $[ll,rr]$ 的信息

代码如下：

inline void Copy(int l,int r,int ll,int rr) {
    It R=split(r+1),L=split(l);
    tot=0;
    for ( It it=L;it!=R;it++ ) {
        b[++tot].l=it->l;
        b[tot].r=it->r;
        b[tot].v=it->v;
    } //用桶记录[l,r]的信息
    It RR=split(rr+1),LL=split(ll);
    S.erase(LL,RR); //清空[ll,rr]这段原有信息
    For(i,1,tot) 
        S.insert((nood){b[i].l-l+ll,b[i].r-l+ll,b[i].v}); //暴力插入
}