浅谈珂朵莉树

Ⅰ 什么是珂朵莉？

珂朵莉是世界上最幸福的女孩，没有之一，不接受任何反驳。

Ⅱ 什么是珂朵莉树？

珂朵莉树又称ODT，是一种基于 $std::set$ 的数据结构，复杂度其实是假的，但是在数据随机的时候可以有很好的表现。

但是珂朵莉树的使用局限性较大，非常好卡，而且如果没有区间赋值操作的话，那就是毫无用武之地。

说白了就是用 $set$ 维护一段连续的相同元素。

Ⅲ 珂朵莉树的实现

1.定义节点

struct Node{
	int l;
    int r;
    mutable ll v;
    bool operator < (const Node &b) const {
        return l < b.l;
    }
};
std::set<Node> s;

我来解释一下各部分吧。

$l, r$ 很显然就是这个区间的左右端点。

$v$ 很显然就是这个区间共同的权值。

顺便说一下 $mutable$ ，这是个黑科技，可以让你对着迭代器直接修改里面不影响顺序的值。

然后下面那个重载运算符就是拿来为了让它在 $set$ 里面的顺序是对的。

哦对，为了方便，我一般习惯加上这么一句：

1	#define iter std::set<Node>::iterator

看后面代码的时候自行脑补一下吧QwQ

2.建树

1 2	for(int i = 1; i <= n; i++) s.insert((Node){i, i, a[i]});

应该不用我多讲，就是把每个点当做一个连续的段暴力插入就行了。

3.核心操作1 $split$

$split$ 操作，顾名思义，就是把原来一段的一个区间分成两段。

一般而言， $split$ 操作都要返回切成的两块区间的右边那段的 $iterator$ 。

iter split(int pos){
    iter it = s.lower_bound((Node){pos, pos, -1}); // 找到它的后一个
    if (it != s.end() && it->l == pos) // 如果根本无需删除，直接return
        return it;
    it--; // 因为找到的是我们需要split的后一个，所以应当分离
    Node ins = *it; // 先把我们要删掉的节点存储好
    s.erase(it); // 分离 = 删除 + 2 * 插入
    s.insert((Node){ins.l, pos - 1, ins.v});
    return s.insert((Node){pos, ins.r, ins.v}).first;
}

个人认为注释里面应该写的比较清楚了QwQ

这应该是最难懂的部分了，如果这部分看懂了接下来的就不难了。

4.核心操作2 $assign$

$assign$ 操作虽然有个很好听的名字：推平一段区间

但是实际上，就是个区间赋值。

那为什么说 $assign$ 操作也是珂朵莉树的核心操作呢？

因为珂朵莉树的复杂度是由它保证的。

一次 $assign$ 操作就会是 $set$ 的规模大幅度减少，而且保证数据随机的情况下， $assign$ 操作出现的概率不小，而且一次的范围也很大，会让 $set$ 的规模一直在一个很小的范围里。（毕竟人家 $split$ 一次才多一个， $assign$ 一下直接一段区间就推平了）

给上代码～

void assign(int l, int r, ll v){
    iter it_r = split(r + 1);
    iter it_l = split(l);
    s.erase(it_l, it_r); // 这样子就可以erase一个区间了
    s.insert((Node){l, r, v});
}

特别短小精悍有木有？

其他常用操作

我们这边就以珂朵莉树公认模板题 $Willem, Chtholly\ and\ Seniorious$ 来做例子了

原题传送门：>Here<

5.区间加

暴力加。

把两端 $split$ 出来，然后，把中间的所有 $iterator$ 里的 $v$ 全都加上 $c$ 。

然后我们之前假的 $mutable$ 标记就可以用上了（

void modify(ll l, ll r, ll c){
    iter it_r = split(r + 1);
    iter it_l = split(l);

    for(iter it = it_l; it != it_r; it++)
        it->v += c;
}

~~又一个一个for循环解决的操作~~

接下来的操作就可以体现出珂朵莉树的强大了。

6.求 $\displaystyle\sum_{i = l}^{r} a_i^x$

ll query(int l, int r, ll x, ll y){
    iter it_l = split(l);
    iter it_r = split(r + 1);
    ll ans = 0;
    for(iter it = it_l; it != it_r; it++){
        ans += (ll)(it->r - it->l + 1) * powmod(it->v, x, y);
        ans %= y;
    }
    return ans;
}

快速幂大家应该都会，~~应该不会有人没学快速幂就来学这种DL数据结构吧~~，我就不贴了。

恩，就是这么暴力，把每段区间取出来，把每个元素的 $x$ 次方算出来，乘上这个连续段的长度，加起来，显然就是答案了。

7.区间第k大

struct Node2{
    ll len;
    ll v;
};
bool cmp(Node2 a, Node2 b){
    return a.v < b.v;
}

ll k_query(ll l, ll r, ll k){
    std::vector<Node2> q;
    q.clear();
    iter it_l = split(l);
    iter it_r = split(r + 1);
    for(iter it = it_l; it != it_r; it++)
        q.push_back((Node2){it->r - it->l + 1, it->v});
    std::sort(q.begin(), q.end(), cmp);
    ll sum = 0;
    for(std::vector<Node2>::iterator it = q.begin(); it != q.end(); it++){
        sum += it->len;
        if(sum >= k)
            return it->v;
    }
    return -1;
}

这个稍微复杂一点，但是实际上还是暴力。

把所有元素取出来，记录一下每个元素出现的数量。

然后把元素排个序，就可以愉快的找到第 $k$ 大了。

至此， $CF896C$ 的所有操作都讲完了。

这边我顺便贴一下 $CF896C$ 的完整代码把

#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define iter std::set<Node>::iterator

ll n, m;
ll seed, vmax;

ll rnd(){
    ll ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}

struct Node{
    ll l;
    ll r;
    mutable ll v;
    bool operator < (const Node &b) const {
        return l < b.l;
    }
};
std::set<Node> s;

iter split(ll pos){
    iter it = s.lower_bound((Node){pos, pos, -1});
    if (it != s.end() && it->l == pos)
        return it;
    it--;
    Node ins = *it;
    s.erase(it);
    s.insert((Node){ins.l, pos - 1, ins.v});
    return s.insert((Node){pos, ins.r, ins.v}).first;
}

void assign(ll l, ll r, ll v){
    iter it_l = split(l), it_r = split(r + 1);
    s.erase(it_l, it_r);
    s.insert((Node){l, r, v});
}

ll powmod(ll a, ll b, ll mod){
    a %= mod;
    ll sum = 1;
    while(b){
        if(b & 1){
            sum *= a;
            sum %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return sum;
}

ll query(ll l, ll r, ll x, ll y){
    iter it_l = split(l);
    iter it_r = split(r + 1);
    ll ans = 0;
    for(iter it = it_l; it != it_r; it++){
        // prllf("[%d %d] -> %d\n", it->l, it->r, it->v);
        ans += (ll)(it->r - it->l + 1) * powmod(it->v, x, y);
        ans %= y;
    }
    return ans;
}

void modify(ll l, ll r, ll c){
    iter it_l = split(l);
    iter it_r = split(r + 1);

    for(iter it = it_l; it != it_r; it++){
        // Node ins = *it;
        // ins.v += c;
        // s.erase(it);
        // s.insert(ins);
        // it = s.find(ins);
        it->v += c;
    }
}

struct Node2{
    ll len;
    ll v;
};
bool cmp(Node2 a, Node2 b){
    return a.v < b.v;
}

ll k_query(ll l, ll r, ll k){
    std::vector<Node2> q;
    q.clear();
    iter it_l = split(l);
    iter it_r = split(r + 1);
    for(iter it = it_l; it != it_r; it++)
        q.push_back((Node2){it->r - it->l + 1, it->v});
    std::sort(q.begin(), q.end(), cmp);
    ll sum = 0;
    for(std::vector<Node2>::iterator it = q.begin(); it != q.end(); it++){
        sum += it->len;
        if(sum >= k)
            return it->v;
    }
    return -1;
}

ll a[100010];

int main(){
    std::cin >> n >> m >> seed >> vmax;
    for(ll i = 1; i <= n; i++)
        a[i] = rnd() % vmax + 1;
    for(int i = 1; i <= n; i++)
        s.insert((Node){i, i, a[i]});
    s.insert((Node){n + 1, n + 1, 0});
    int cnt = 0;
    for(ll i = 1; i <= m; i++){
        ll type = (rnd() % 4) + 1;
        ll l = (rnd() % n) + 1;
        ll r = (rnd() % n) + 1;
        ll x, y;

        if(l > r)
            std::swap(l, r);
        if(type == 3)
            x = (rnd() % (r - l + 1)) + 1;
        else
            x = (rnd() % vmax) + 1;
        if(type == 4)
            y = (rnd() % vmax) + 1;

        if(type == 1){
            modify(l, r, x);
        } else if(type == 2){
            assign(l, r, x);
        } else if(type == 3){
            printf("%I64d\n", k_query(l, r, x));
            cnt++;
        } else if(type == 4){
            printf("%I64d\n", query(l, r, x, y));
            cnt++;
        }
    }
}

~~为什么感觉一大半代码都是随机数生成器的~~

Ⅳ 可以使用珂朵莉树的其他题目

例题1

给定一个仅包含小写字母的字符串。

资瓷区间排序

求 $m$ 次排序之后的字符串。

这题的正常做法是线段树维护一个桶，然后在排序的时候进行26次的查询与修改。

这样的话虽然理论复杂度是 $O(n \log n)$ 的，但是带一个 $26$ 的大常数，极易造成卡常。

如果使用珂朵莉树的话，我们可以用类似这种线段树的做法，查询每个字母出现的数量，再进行26次区间修改操作。

于是我们可以发现，一次排序之后，这一段区间最后只会被分成 $26$ 个 $set$ 中元素，规模完全可以接受。

实测在数据随机的情况下，珂朵莉树暴打 $O(n \log * 26)$ 的标算。

（这是我们某次模拟赛的题目）

（结果标算T飞了，时限开到7s都拯救不了，而某位dalao同学spfa使用珂朵莉树A了，A了就算了，还快的飞起，于是该同学之后不久改名叫做Chtholly_Tree，并留下一句名言：）

模拟赛使我相信珂学。

例题2

>Here<

一个长度为 $10^9$ 的0-1串，初始值全为 $1$

资瓷区间修改为0或者为1

求每次修改之后 $1$ 的个数。

这道题目正统做法是动态开点线段树。

但是显然区间修改让我们往珂朵莉树方面去想

我们只需要让珂朵莉树资瓷 $assign$ 还有区间求和就行了

Ⅴ 总结-珂朵莉树的优缺点

优点：

码量小
易于理解
能够资瓷大量操作

缺点：

使用局限性较大
容易被卡

珂朵莉树的功能极其强大，可以说只要可以暴力做的它都能做，但是只要没有区间复制操作，那么它比暴力还多只 $\log$ ，而且只要出题人有这个心，完全可以把你卡满，但是它作为一种骗分技巧还是非常实用的，很重要的是它学起来很简单，而且大概 $10min$ （也许更短？）就可以敲完。

Dilute