求赞QAQ

珂朵莉树是我在上个月学的，因为那时在准备毕业考才没有做这个分享，现在来填坑

总写和作用

珂朵莉树(又称颜色段均摊)是一位$dalao$在$\text{CF}$一次比赛上发明的
可以使用珂朵莉树的条件是:
1. 要有区间复制操作
2. 数据保证完全随机

但在一般情况下作为一些数据结构毒瘤题的骗分方式，一般能过$80pts$以上

存储

使用一个有结构体的$set$来完成

struct Node
{
    int l, r; //颜色为v的连续区间的左端点和右端点
    mutable int v; //注意要加mutable

    bool operator < (const Node& t) const //重载按左端点排序
    {
        return l < t.l;
    }
};

typedef set<Node>::iterator iter;

set<Node> ODT;

$\text{split}$操作

作用:将包含$x$的区间分为$l \sim x - 1$和$x \sim r$两端，返回后一段的迭代器
用二分查找即可

iter split(int x)
{
    if (x > n) return ODT.end();
    auto it = -- ODT.upper_bound({x, 0, 0}); //二分查找

    if (it -> l == x) return it; //左端点就是x返回

    int l = it -> l, r = it -> r, v = it -> v;
    ODT.erase(it); //删除原区间
    ODT.insert({l, x - 1, v}); //将区间分成l~x-1和x~r两端
    return ODT.insert({x, r, v}).first; //返回后一段迭代器
}

$\text{Q}$: 为什么要这样分?
$\text{A}$: 因为迭代器遍历是左闭右开的,在区间操作中使代码简化

$\text{assign}$操作

这是珂朵莉树维持复杂度的核心
遇到区间推平操作来将两端合并减少复杂度

void assign(int l, int r, int x) //将l~r区间的数改为x
{
    auto itr = split(r + 1), itl = split(l); //要先split r+1 在 split l,否则会RE
    ODT.erase(itl, itr); //删除l~r+1的区间 (不包含r+1)
    ODT.insert({l, r, x}); //插入l~r颜色为x的区间
}

其他操作和时间复杂度分析

其他操作就照这个来

int query(int l, int r)
{
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl ++ )
    //  do something
}

时间复杂度分析: 用$set$的珂朵莉树是$O(n \log \log n)$，就是线性复杂度(参照oi-wiki)
如果要维护两个或以上的信息，还有在来一个线段树或平衡树辅助维护

例题1 P1558 色板游戏

简化题意:
让你维护一个序列，支持以下操作
1. 将l~r的颜色改为x
2. 求l~r中不同颜色的个数

正解是线段树+状态压缩，这里使用珂朵莉树骗分
直接基础操作就可以了

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

const int N = 35;

struct Node
{
    int l, r;
    mutable int v;

    bool operator < (const Node& t) const
    {
        return l < t.l;
    }
};

typedef set<Node>::iterator iter;

set<Node> ODT;
int n, m, k;

iter split(int x)
{
    if (x > n) return ODT.end();
    auto it = -- ODT.upper_bound({x, 0, 0});

    if (it -> l == x) return it;

    int l = it -> l, r = it -> r, v = it -> v;
    ODT.erase(it);
    ODT.insert({l, x - 1, v});
    return ODT.insert({x, r, v}).first;
}

void assign(int l, int r, int x)
{
    auto itr = split(r + 1), itl = split(l);
    ODT.erase(itl, itr);
    ODT.insert({l, r, x});
}

int query(int l, int r)
{
    static int cnt[N] = {0};
    memset(cnt, 0, sizeof cnt);

    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; itl ++ )
        cnt[itl -> v] ++ ;

    int res = 0;
    for (int i = 1; i <= k; i ++ )
        if (cnt[i])
            res ++ ;
    return res;
}

int main()
{
    scanf("%d%d%d", &n, &k, &m);
    ODT.insert({1, n, 1});

    while (m -- )
    {
        char op[2];
        int l, r, v;
        scanf("%s%d%d", op, &l, &r);

        if (l > r) swap(l, r);
        if (*op == 'C')
        {
            scanf("%d", &v);
            assign(l, r, v);
        } else printf("%d\n", query(l, r));
    }

    return 0;
}

这样就可以拿到$100pts$的好成绩($hack$数据会$T$)
上图:

例2 P5251 [LnOI2019]第二代图灵机

不要看见黑题就怕，其实这道题还挺好想的
数字用线段树维护，颜色用珂朵莉树
对于操作1.2,直接在线段树和珂朵莉树上修改
对于操作3.4,用珂朵莉树双指针维护，用线段树查询(注意查询区间为开区间)
由于数据随机,所以这个代码能通过，复杂度$O(n \log \log n + n \log n)$

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

void read(int &x)
{
    char ch;
    while (ch = getchar(), ch < '!'); x = ch - 48;
    while (ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}

const int N = 100010, M = 110, INF = 0x3f3f3f3f;

int n, m, k, w[N], cnt[M];
int tot;

struct Segment //线段树
{
    int l, r;
    int maxv, minv;
    int sum;
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
    tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[l], w[l], w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;

        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int v)
{
    if (tr[u].l == tr[u].r) tr[u].maxv = tr[u].minv = tr[u].sum = v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int query_max(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;

    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;

    if (l <= mid) res = max(res, query_max(u << 1, l, r));
    if (r > mid) res = max(res, query_max(u << 1 | 1, l, r));

    return res;
}

int query_min(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].minv;

    int mid = tr[u].l + tr[u].r >> 1;
    int res = INF;

    if (l <= mid) res = min(res, query_min(u << 1, l, r));
    if (r > mid) res = min(res, query_min(u << 1 | 1, l, r));

    return res;
}

int query_sum(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;

    if (l <= mid) res += query_sum(u << 1, l, r);
    if (r > mid) res += query_sum(u << 1 | 1, l, r);

    return res;
}

/* ------------------------------ */

struct Node //珂朵莉树
{
    int l, r;
    mutable int v;

    bool operator < (const Node& t) const
    {
        return l < t.l;
    }
};

typedef set<Node>::iterator iter;
set<Node> ODT;

iter split(int x)
{
    if (x > n) return ODT.end();
    auto it =  -- ODT.upper_bound({x, 0, 0});

    if (it -> l == x) return it;

    int l = it -> l, r = it -> r, v = it -> v;
    ODT.erase(it);
    ODT.insert({l, x - 1, v});
    return ODT.insert({x, r, v}).first;
}

void assign(int l, int r, int v)
{
    auto itr = split(r + 1), itl = split(l);
    ODT.erase(itl, itr);
    ODT.insert({l, r, v});
}

/* ------------------ */

void add(int x)
{
    if (!cnt[x]) tot ++ ;
    cnt[x] ++ ;
}

void del(int x)
{
    cnt[x] -- ;
    if (!cnt[x]) tot -- ;
}

int query_all(int l, int r) //操作3
{
    if (k == 1) return query_min(1, l, r); //处理边界

    auto itr = split(r + 1), itl = split(l), it = itl;
    tot = 0;
    int res = INF;
    memset(cnt, 0, sizeof cnt);

    while (it != itr) //双指针
    {
        add(it -> v); //加上颜色
        while (tot == k)
            res = min(res, query_sum(1, itl -> r, it -> l)), del((itl ++ ) -> v); //询问数值，删除左端点颜色
        it ++ ;
    }

    if (res == INF) return -1;
    return res;
}

int query_unique(int l, int r) //操作4
{
    auto itr = split(r + 1), itl = split(l), it = itl;
    int res = query_max(1, l, r); //边界问题
    memset(cnt, 0, sizeof cnt);

    while (it != itr)
    {
        cnt[it -> v] ++ ;
        while (it != itl && cnt[it -> v] > 1) cnt[(itl ++ ) -> v] -- ; //双指针

        if (it != itl) res = max(res, query_sum(1, itl -> r, it -> l));
        if (it -> l != it -> r) //长度>1的段不合法，直接跳过
            while (itl != it)
                cnt[(itl ++ ) -> v] -- ;
        it ++ ;
    }

    return res;
}

int main()
{
    read(n), read(m), read(k);
    for (int i = 1; i <= n; i ++ ) read(w[i]);
    ODT.insert({1, n, 0});
    for (int i = 1, x; i <= n; i ++ ) read(x), assign(i, i, x);

    build(1, 1, n);
    while (m -- )
    {
        int op, l, r, v;
        scanf("%d%d%d", &op, &l, &r);

        if (op == 1) modify(1, l, r);
        if (op == 2)
        {
            scanf("%d", &v);
            assign(l, r, v);
        }
        if (op == 3) printf("%d\n", query_all(l, r));
        if (op == 4) printf("%d\n", query_unique(l, r));
    }

    return 0;
}