我可爱的珂朵莉树

我可爱的珂朵莉树

• 珂朵莉树又名

• 在数据随机的情况下极其优秀，会有些意想不到的结果

• 思维简单暴力，操作简单粗暴

实现原理

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

实现方式

• 初始化

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

代码如下：

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;

• 的两个重要操作

对于操作的原理就是把这段区间分成两端区间，返回的迭代器。直接用二分找出所在区间即可。

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

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; //加入新增的
}

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

这种操作就是先把区间的值变为,再把这个区间推平变成上的一个点。关键在于由于大部分题目数据随机所以上的点会快速减少所以此时的复杂度接近

代码如下：

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});
}

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

区间加

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;
}

区间求和

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;
}

区间覆盖

就是把这段区间覆盖到上面去

这是我们有个简单粗暴的方法就是先记个桶先把区间里的信息记到桶里去再用这个桶的信息去修改的信息

代码如下：

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}); //暴力插入
}

的几道题目

CF896C Willem, Chtholly and Seniorious

代码：CF896C

P5350 序列

代码：P5350

P2787 语文1（chin1）- 理理思维

代码：P2787

P4979 矿洞：坍塌

代码：P4979