颜色段均摊，珂朵莉树

珂朵莉树，又名ODT。暴力数据结构。

前置芝士

会用STL的set就行。

原理

珂朵莉树把一个区间看做一个节点扔到set里来保证随机情况下的复杂度。

所以这玩意其实叫颜色段均摊。因为需要有个随机的区间推平（就是赋值）操作来保证均摊复杂度正确性。

另外这玩意拿set维护是均摊 \(O(n\log\log n)\) 的，拿链表是 \(O(n\log n)\) 的。

CF896C Willem, Chtholly and Seniorious

珂朵莉树板子。

节点

珂朵莉树的节点长这个样子：

struct node{
    int l,r;
    mutable int val;
    bool operator<(const node &s)const{
        return l<s.l;
    }
};
set<node>s;

这个mutable是“可变的”，也就是可以直接改set里面的值。这个东西代表了区间 \([l,r]\) 的值为 \(val\) 。

Split

珂朵莉树的核心操作，作用是把原来包含 \(pos\) 这个位置的区间 \([l,r]\) 在 \(pos\) 断开为 \([l,pos)\) 和 \([pos,r]\) ，然后返回指向 \([pos,r]\) 的迭代器。

set<node>::iterator split(int pos){
    set<node>::iterator it=s.lower_bound({pos,0,0});//查找pos位置
    if(it!=s.end()&&(*it).l==pos)return it;//pos为左端点直接返回
    --it;
    if((*it).r<pos)return s.end();
    int l=(*it).l,r=(*it).r,val=(*it).val;
    s.erase(it);
    s.insert({l,pos-1,val});//裂开
    return s.insert({pos,r,val}).first;//insert返回一个pair 第一个是迭代器 第二个是是否插入成功
}

然后就是这个题里的一些操作。

区间加

把左右端点裂开然后中间所有段暴力加上就行。

void update(int l,int r,int val){
    set<node>::iterator itr=split(r+1),itl=split(l);
    for(set<node>::iterator it=itl;it!=itr;++it)(*it).val+=val;
}

区间推平

仍然把区间裂开，然后由于这个区间成了一个值所以中间的段可以都去掉了，最后插入这一段。

void assign(int l,int r,int val){
    set<node>::iterator itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert({l,r,val});
}

第k小

大力模拟。把中间所有东西塞进一个vector，排序后暴力查找。

struct rk{
    int val,cnt;
    bool operator<(const rk &s)const{
        return val<s.val;
    }
};
int rnk(int l,int r,int k){
    set<node>::iterator itr=split(r+1),itl=split(l);
    vector<rk>v;
    for(set<node>::iterator it=itl;it!=itr;++it){
        v.push_back({(*it).val,(*it).r-(*it).l+1});
    }
    sort(v.begin(),v.end());
    int i;
    for(i=0;i<v.size();i++){
        if(v[i].cnt<k)k-=v[i].cnt;
        else break;
    }
    return v[i].val;
}

区间pow

裂开以后暴力快速幂。

int getpow(int l,int r,int x,int mod){
    set<node>::iterator itr=split(r+1),itl=split(l);
    int ans=0;
    for(set<node>::iterator it=itl;it!=itr;++it){
        ans=(ans+1ll*qpow((*it).val,x,mod)*((*it).r-(*it).l+1)%mod)%mod;
    }
    return ans;
}

别忘了初始化，每个元素自己是一段。如果初始为空就插入一个全零区间。

然后关于时间复杂度的问题去找joke3579和jijidawang。这里来点不一样的。

一些不一样的操作

现在没有随机了。也没有什么区间推平操作。

但是我们可以允许扔掉 \(O(n\log\log n)\) 的复杂度。根号就行。

然后给你点分块维护不来的操作，比如[模板]文艺平衡树。

我们当然可以用块状链表。但是这玩意常数贼大。有没有什么方法砍树剪枝？

其实可以珂树。

现在没有区间赋值就不要用什么set了，常数太大。直接上链表。我们知道链表维护的珂朵莉树在一开始没几块的时候Split是非常迅速的。但是后面散块太多了就会非常辣鸡。

解决的方法其实很简单，根号拍扁重构就行了。

拿文艺平衡树举例子。我们对下标维护一堆段，每段都是一个公差为 \(\pm 1\) 的序列。初始的时候显然只有一个 \(1-n\) 的公差为 \(1\) 的序列。每次翻转一个区间的时候Split出来，把中间的所有段暴力翻过来然后段内打标记。块数大于根号时把所有段拆开更改原序列，然后重新建一个只有一段的珂树。

这玩意貌似跑的飞快，现在的最优解就是这个。

再来一个，区间加，区间求和，然后给你一个单点插入操作。为了按死线段树平衡树离线建序列给了个强制在线。

对原数列做个前缀和，然后开个空的珂树，区间加的时候直接暴力Split然后打标记，单点插入的时候打个标记告诉它这个是个单点就行了。区间求和的时候原数列前缀和加上珂树里的标记。记得根号重构。

这玩意貌似可以维护一堆其他奇奇怪怪的操作（比如区间带插入众数）和大部分块链能搞的东西，而且常数贼小。但是有时候复杂度会比块链大点。比如带插区间第k小这个题，为了平衡三种操作的复杂度这玩意变成了 \(O(n^{\frac 53})\) 。

总之这玩意可以维护这样一类东西：数列相对稳定（或者区间查询很快，比如文艺平衡树）（所以这玩意没法搞文艺平衡树+区间第k小），能很快求出静态情况下的答案（方便和珂树答案拼起来）。

相对科技。没敢实现。