珂朵莉树学习笔记

fly_fire · 2025-03-21 19:15:46 · 算法·理论

前言

终于学到了比分块更加美丽暴力的数据结构。一是因为它比分块更加暴力，二是珂朵莉本来就很美丽。

我 TM 从 oiwiki 上学的代码还能不一样吗？？？

原理

珂朵莉树（odt），又名颜色段均摊。它维护的每一个区间里都是相同的数据。例如序列 1 2 2 3 4 1 在 odt 中就使用 5 个区间维护。

由于 odt 需要频繁的插入和删除区间，所以通常选择 set 维护。set 里是一些结构体维护的区间，又因为区间的数据需要修改，所以区间的数值 v 前面要加上关键字 mutable。

下面是定义 odt 的示例。

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

    Node(int x, int y, int z) {
        l = x, r = y, v = z;
    }

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

set<Node> odt;

初始化的时候因题目而异，有时插入一个 1 到 n 的区间（值是题目给定的）。有时把每个数当作一个长度为 1 的区间插入进去。

然后是 odt 的核心操作 split 和 assign。

split 操作

split 做的事就是找到 x 所在的区间 [l,r]，并且把这个区间分裂成 [l,x - 1] 和 [x,r]，然后返回分裂完的右区间的迭代器。

首先查找 x 所在的区间，直接用 lower_bound 暴力找就好了（对就是这么暴力）。由于用区间的 l 作为第一关键字，找到的区间要么左端点是 x，此时就不用分裂了，直接 return；要么是包含 x 的区间的下一个区间，此时上一个区间就是要找的区间，迭代器自减。

找到区间之后直接把它 erase 掉，再插入 [l,x - 1] 和 [x,r]。

于是 split 操作结束。

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});//按第一关键字排序，后面两个随便填
    if (it != odt.end() && it -> l == x) return it;//如果当前区间的左端点就是这个区间
    it--;//否则要找的就是上一个区间
    int l = it -> l, r = it -> r, v = it -> v;//要先把当前区间的信息记录下来，erase 掉后就用不了了。   
    odt.erase(it);
    odt.insert({l, x - 1, v});
    return odt.insert({x, r, v}).first;
}

assign 操作

此操作完成的事很简单，就是把区间 [l,r] 推平，并赋值成 v。

这个操作直接利用 split 完成就很简单，具体见代码注释。

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
//注意先split(r + 1)，再split(l)，因为如果先把左边的区间 erase 掉再找右边的区间会出问题
//再注意理解为什么是 r + 1 而不是 r
//需要操作的区间是到 r 的，所以 split 时为了把 r 点包含进去应该 split 到 r + 1。
    odt.erase(itl, itr);
    odt.insert({l, r, v});
}

其他操作

其他操作就是题目中给定的各种操作。先把要操作的区间 split 出来，再进行各种修改和查询操作就好了。

void myfunction(int l, int r, int x) {
    auto itr = split(r + 1), itl = split(l);
    for (;itl != itr;itl++) {
        //各种操作各种操作各种操作
    }
}

odt 的应用

CF896C Willem, Chtholly and Seniorious

珂朵莉起源题对吧。

对于操作 1 和 2 是很好用珂朵莉树维护的。考虑操作 3 和 4 怎么完成（虽然似乎不用怎么考虑）。

对于操作 3，我们直接将每个值和这个值的个数加到 vector 里面，然后直接 sort 一遍，接着遍历一遍找到 k 大值。

对于操作 4 （k 方和）就是很经典的求和操作了。对于每一个值分别求它的幂，然后加起来就好了。

于是这道题迎刃而解。

#include<bits/stdc++.h>

#define int long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;
typedef pair<int, int> PII;

int n, m, seed, Vmax;

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

    Node(int x, int y, int z) {
        l = x, r = y, v = z;
    }

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

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    if (r < x) return odt.end();    
    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 l, int r, int x) {
    auto itr = split(r + 1), itl = split(l);
    for (;itl != itr;itl++) itl -> v += x;
}

int len(auto it) {
    return it -> r - it -> l + 1;
}

int qpow(int a, int p, int mod) {
    int ans = 1;a %= mod;
    while (p) {
        if (p & 1) ans *= a, ans %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }
    return ans;
}

int query(int l, int r, int p, int mod) {
//  cout << l << ' ' << r << ' ' << p << ' ' << mod;
    auto itr = split(r + 1), itl = split(l);
    int cnt = 0;
    for (;itl != itr;itl++) cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
    return cnt;
}

int kth(int l, int r, int k) {
    vector<PII> a;
    auto itr = split(r + 1), itl = split(l);
    for (auto iter = itl;iter != itr;iter++) a.push_back(PII(iter -> v, (iter -> r) - (iter -> l) + 1));
    sort(a.begin(),a.end());
    for (auto iter = a.begin();iter != a.end();iter++) {
        k -= iter -> second;
        if (k <= 0) return iter -> first;
    }
    return -1;
}

int rnd() {
    int ret = seed;
    seed = (seed * 7 + 13) % (long long)(1e9 + 7);
    return ret;
}

signed main() {
    n = read(), m = read(), seed = read(), Vmax = read();
    for (int i = 1;i <= n;i++) odt.insert(Node(i, i, (rnd() % Vmax) + 1));

    while (m--) {
        int op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, y;
        if (l > r) swap(l, r);
        if (op == 3) x = (rnd() % (r - l + 1)) + 1;
        else x = (rnd() % Vmax) + 1;
        if (op == 4) y = (rnd() % Vmax) + 1;

        switch (op) {
            case 1 : {add(l, r, x);break;}
            case 2 : {assign(l, r, x);break;}
            case 3 : {write(kth(l, r, x)), putchar(10);break;}
            case 4 : {write(query(l, r, x, y)), putchar(10);break;}
            default : break;
        }

//      for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
    }

    return 0;
}

注意这个快速幂里面底数先要模模数，否则会 WA #3。

P3071 [USACO13JAN] Seating G

什么？最左的连续空位？还有区间推平？ 于是自然想到珂朵莉树解决。

初始化时先插入一个 1 到 n，值为 0 的区间，表示初始全为空座位。

找最左的连续 a 个空位，直接暴力循环一遍就好了，别忘了把相邻的空区间的长度累加起来，否则就会 WA 20pts。

客人离开就是区间推平，直接 assign 即可。

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 5e5 + 5;

int n, m;

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

    Node(int L, int R, int V) {l = L, r = R, v = V;}

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

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, val = it -> v;
    if (r < x) return odt.end();
    odt.erase(it);
    odt.insert(Node(l, x - 1, val));
    return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int len(auto x) {
    return x.r - x.l + 1;
}

int update(int x) {
//  auto rit = split(y + 1), lit = split(x);
//  for (auto i : odt) {
//      if (i.v == 1) continue;
//      if (len(i) >= x) {
//          Assign(i.l, i.l + x, 1);
//          return 0;
//      }
//  }

    int tot = 0, cnt = 0, frm = -1;
    for (auto i : odt) {
        if (i.v == 0) {
            cnt += len(i);
            if (frm == -1) frm = i.l;
        }
        else cnt = 0, frm = -1;
        tot = max(tot, cnt);
        if (tot >= x) {
            Assign(frm, frm + x - 1, 1);
            return 0;
        }
    }
    return 1;
}

int main() {
    n = read(), m = read();

    odt.insert(Node(1, n, 0));

    int ans = 0;
    while (m--) {
        char ch;cin >> ch;
        int x = read(), y;
        if (ch == 'A') ans += update(x);
        else y = read(), Assign(x, y, 0); 
//      for (auto i : odt) {
//          cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//      }
    }

    write(ans), putchar(10);
    return 0;
}

P4344 [SHOI2015] 脑洞治疗仪

众所周知的，这道题被卡了对吧。所以这是 100 pts 做法（unaccepted）。

操作 0 就是推平，操作 1 用 vector 记下来再填进去（注意 split 和 erase 之间的顺序），操作 2 就类似上一题的做法统计最长的空区间。

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 2e5 + 5;

int n, m;

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

    Node(int L, int R, int V) {
        l = L, r = R, v = V;
    }

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

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound(Node(x, 0, 0));
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, val = it -> v;
    if (r < x) return odt.end();
    odt.erase(it);
    odt.insert(Node(l, x - 1, val));
    return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert(Node(l, r, val));
}

int len(auto x) {
    return x -> r - x -> l + 1;
}

void update(int l1, int r1, int l2, int r2) {
    auto rit = split(r1 + 1), lit = split(l1), L = lit;
//  int cnt = 0;
//  for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit), lit -> v = 0;

    int cnt = 0;
    for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit);
    Assign(l1, r1, 0);
//  for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//  putchar(10);
    rit = split(r2 + 1), lit = split(l2);
    for (;lit != rit;lit++) {
        if (lit -> v == 1) continue;
        if (cnt >= len(lit)) cnt -= len(lit), lit -> v = 1;
        else {
            if (cnt != 0) Assign(lit -> l, lit -> l + cnt - 1, 1);
            break;
        }
    }
}

int perform(int l, int r) {
    auto rit = split(r + 1), lit = split(l);
    int ans = 0, cnt = 0;
    for (;lit != rit;lit++) {
//      cout << lit -> l << ' ' << lit -> r << ' ' << lit -> v << '\n';
        if (lit -> v == 0) cnt += len(lit);
        else ans = max(ans, cnt), cnt = 0;
    }
    ans = max(ans, cnt);
    return ans;
}

int main() {
    n = read(), m = read();

    odt.insert(Node(1, n + 1, 1));

    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 0) Assign(x, y, 0);
        if (op == 1) {
            int u = read(), v = read();
            update(x, y, u, v);
        }
        if (op == 2) write(perform(x, y)), putchar(10);
    }

    return 0;
}

P7134 小 H 的序列

https://www.luogu.com.cn/problem/P7134。

这个查询操作看起来十分像珂朵莉树的起源题对吧，所以自然想到珂朵莉树解决。

操作一似乎不能直接推平，考虑把每个区间转存到数组里面，再把操作区间删掉，然后把相邻且值相同的区间合并之后再加到珂朵莉树中。

询问操作就是很典的珂树了，把每个树里的的区间一起计算 v ^ {p}，再乘上区间长度，累加到答案。

#include<bits/stdc++.h>

#define int unsigned long long

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;

int n, m;

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

//  Node(int x, int y, int z) {
//      l = x, r = y, v = z;
//  }

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

set<Node> odt;

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if (it != odt.end() && it -> l == x) return it;
    it--;
    int l = it -> l, r = it -> r, v = it -> v;
    if (r < x) return odt.end();    
    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});
}

int MOD[maxn], Val[maxn];
int qpow(int a, int p, int mod) {
    int ans = 1LL, A = a;

    if (MOD[A] == mod) return Val[A];

    while (p) {
        if (p & 1) ans *= a, ans %= mod;
        a *= a, a %= mod;
        p >>= 1;
    }

    Val[A] = ans, MOD[A] = mod;

//  cout << ans << '\n'; 
    return ans % mod;
}

void update(int l, int r, int x, int y, int d) {
//  cout << l << ' ' << r << ' ' << x << ' ' << y << ' ' << d << '\n';
    auto itr = split(r + 1), itl = split(l);Node its[maxn];
    int tot = 1, nowx = 0;
    for (auto i = itl;i != itr;i++) {
        int v = i -> v;
        its[++tot] = *i;
        if (v <= y && v >= x) its[tot].v = d;
    }

    odt.erase(itl, itr);

    for (int i = 1;i <= tot;i++) {
        if (i == 1 || its[i].v != its[i - 1].v) {
            if (nowx) odt.insert({nowx, its[i - 1].r, its[i - 1].v});
            nowx = its[i].l;
        }
    }
    odt.insert({nowx, r, its[tot].v});
}

int len(auto it) {
    return it -> r - it -> l + 1;
}

int query(int l, int r, int p, int mod) {
//  cout << l << ' ' << r << ' ' << p << ' ' << mod << '\n';
    auto itr = split(r + 1), itl = split(l);
//  cout << itl -> l << ' ' << itr -> r;
    int cnt = 0;
    for (;itl != itr;itl++) {
//      cout << itl -> l << ' ' << itl -> r << ' ' << itl -> v << ' ' << len(itl) << '\n';
//      (((cnt += qpow(itl -> v, p, mod)) %= mod) *= len(itl)) %= mod;
        cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
//      cout << qpow(itl -> v, p, mod) << "nailong " << cnt << '\n';
    }
//  cout << cnt << '\n';
    return cnt;
}

signed main() {
    n = read(), m = read();

    for (int i = 1;i <= n;i++) odt.insert({i, i, read()});

    int Ans = 0;

    while (m--) {
        int op = read(), l = read(), r = read(), u = read(), v = read(), t;
        if (op == 0) t = read(), update(l, r, u, v, t);
        else Ans ^= query(l, r, u, v);

//      for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
    }

    write(Ans), putchar(10);

    return 0;
}