wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

可持久化线段树

树链剖分

平衡树

FHQ-Treap

珂朵莉树

[[ item.c ]]

珂朵莉树

## 珂朵莉树算法思想
经常用于处理，随机数据下，把**一整段区间**赋值成相同的数，类似的问题

### 结构体定义
随机数据，并且处理一些线段树难以维护的操作，比如带修改的$$\sum\_{i=l}^{r} a\_{i}^{x}$$
另外珂朵莉树还可以维护带修改的
```bash
1.区间加
2.区间第 k 小
3.区间次幂和
```

数据结构的定义如下
```bash
struct Node {
    i64 l, r;
    mutable i64 v;
    Node(i64 l, i64 r, i64 v) : l(l), r(r), v(v) {}
    inline bool operator< (const Node &rhs) const {
        return l < rhs.l;
    }
};
```

实际上，结构体中定义了`l, r, v`，`l, r`分别表示区间的左右端点，**这里一般用闭区间 + lower_bound**，即`[l, r]`
另外还有一个`v`，表示区间中我们需要维护的值

### 算法实现
> 假设操作`[l, r]`区间，但是在`set`中不存在，怎么办？

假设我们已经有两个区间`[0, 2], [3, 10]`，但是需要对`[5, 8]`执行区间修改，怎么办？

**分裂操作**
可以把`[3, 10]`拆分，拆成`[3, 4] + [5, 8] + [9, 10]`，然后对`[5, 8]`操作即可

**合并操作**
假如我们有若干区间`[1, 3] + [4, 10] + [11, 19] + ...... + [98, 102] + [103, 109]`
但是我们需要对`[2, 100]`区间修改，怎么办？

找到最左边的，包含`[2, 100]`的区间
（二分左端点`lower_bound(2)`即可，发现是`[4, 10], 4 > 2`，回退一步），找到`[1, 3]`
按`2`分裂，形成区间`[1, 1] + [2, 3] +.....`，迭代器指向`[2, 3]`

然后找到最右边的，包含`[2, 100]`的区间
（二分**右端点 + 1** 的位置`lower_bound(101)`，发现是`[103, 109], 103 > 101`，回退一步），找到`[98, 102]`
按`101`分裂，形成区间`[98, 100] + [101, 102] `，迭代器指向`[101, 102]`

我们让迭代器指向`itl = [2, 3]`以及`itr = [101, 102]`，那么`[itl, itr)`区间里的数不需要了
把区间的数全部删除，最后插入我们新的区间`[2, 100]`，这样就完成了合并操作

#### Split
对于整数$$x$$，找到包含$$x$$的区间，将其拆分成$$[l, x-1] \cup [x, r]$$两个区间，并且返回**后者**的迭代器
`split(x)`，返回的迭代器，指向的区间`l = x`
```bash
auto split = [](int x) {
    // [l, r] -> [l, x-1] + [x, r], x 是下标，返回指向 [x, r] 的迭代器
    auto it = odt.lower_bound(Node(x, 0, 0));

if (it != odt.end() && it->l == x) return it;
    --it;

// it=[l, r] --> [l, x-1] + [x, r]
    auto [l, r, v] = *it;

odt.erase(it);
    
    odt.insert(Node(l, x-1, v));
    return odt.insert(Node(x, r, v)).first;
};
```

#### assign
根据之前的分析，我们对区间`[l, r]`赋值操作的时候，可以将其转化成`[split(l), split(r+1)) = [itl, itr)`
然后**删除**`[itl, itr)`，同时**构造一个新的**段`[l, r]，值为 v`，插入到`set`中

```bash
auto assign = [](int l, int r, i64 v) {
    // [l, r] -> 赋值为 v
    auto itr = split(r+1), itl = split(l);
    odt.erase(itl, itr);

odt.insert(Node(l, r, v));
};
```

> 特别注意，必须先`split(r+1)`，再`split(l)`，为什么呢？因为`l, r`可能位于同一个段`[x, y]`上
而如果你先`split(l)`，先找到`[x...l...r...y]`这个段，然后删除，再插入`[x, l-1] + [l..r.. y]`
如果你再进行`split(r)`，那么会导致什么问题呢？`it`本来应该指向`[l...r...y]`的
而现在`[l...r...y]->[l, r-1]+[r, y]`，原先的迭代器被释放了，也就是`itl`指向空指针

**所以，一定要**先`split(r+1)`再`split(l)`

## 珂朵莉树的应用
### Codeforces Round 449
#### C
**[C. Willem, Chtholly and Seniorious](https://codeforces.com/contest/896/problem/C)**
**问题描述**
写一种数据结构，支持
```bash
1 l r x，将 [l, r] 区间所有数都 +x
2 l r x，将 [l, r] 区间所有数都赋值成 x
3 l r x，输出将 [l, r] 区间从小到大排序之后第 x 小的元素是多少？相等算多次
4 l r x y, 输出 [l, r] 区间每个数的 x 次幂 mod y 的值
```
形式化地，第四种操作 $$\displaystyle \left( \sum\_{i = l}^{r} a_i^x \right) \bmod y$$

**算法分析**
赋值操作，很显然就是`assign`，下面着重考虑区间加，区间乘方，kth这三种操作

**区间加**
实际上，对`[l, r]`区间加，实际上返回两个迭代器`[itl, itr) = [split(l), split(r+1))`
只需要暴力地对`[itl, itr)`之间所有的段，执行区间加即可

**幂指和**
幂指和也是暴力，对于`[itl, itr)`之间的每一个段`i`，都代表一个区间段`[i.l, i.r]`，这一整段的值都是`i.v`
那么这一段的贡献实际上是$$(i.v)^x \cdot (i.r - i.l + 1)$$，暴力计算每一段即可

**区间第 k 大**
同样`[itl, itr) = [split(l), split(r+1))`，对于区间中的每一段`[i.v,  len = i.r - i.l + 1]`，都用一个`vector`存起来
其中`len = i.r - i.l + 1`表示区间内有多少个元素？

对`vector`按`i.v`排序，然后遍历`vector`，`k -= len`，当`k <= 0`的时候，返回当前的`i.v`即可

> 不难发现，珂朵莉树需要数据随机，才能保证复杂度，如果每个数都不同，那么复杂度很可能会爆炸

### leetcode 第 285 场周赛
#### D
**[由单个字符重复的最长子字符串](https://leetcode.cn/contest/weekly-contest-285/problems/longest-substring-of-one-repeating-character/description/)**
**问题描述**
给定一个下标从`0`开始的字符串`s`，另外再给你一个下标从`0`开始，长度为`k`的字符串`queryCharacters`
还有一个下标从`0`开始，长度也是`k`的整数**下标数组**`queryIndices`，两个都用来描述`k`次查询

第`i`次查询，将`s`中，位于下标`queryIndices[i]`的字符，修改成`queryCharacters[i]`

现在要你返回一个长度为`k`的数组`length`，其中`length[i]`表示第`i`个查询后，`s`中仅由**单个重复字符**组成的最长连续子串的长度

**算法分析**
如果用线段树，那么是很标准的线段树操作
每个节点维护`maxlen`表示区间最长相同字符子串的长度，同时还要维护
`pre = (ch, prelen)`，表示区间前缀以`ch`打头，最长相同前缀是`prelen`
`suf = (ch, suflen)`，表示区间后缀以`ch`结尾，最长相同后缀是`suflen`

区间合并的时候，如果左儿子的`pre = (ch, prelen = 左儿子的区间长度)`
那么如果还有`左儿子的 ch = 右儿子的 ch`的时候，左右儿子的`prelen`可以合并
否则当前的`prelen`就等于左儿子的`prelen`
后缀也是类似的

`maxlen`是`3`部分取`max`
```bash
1.左儿子的 maxlen
2.右儿子的 maxlen
3.如果左儿子的 suf = (chl, suflen) 和右儿子的 pre = (chr, prelen)，满足 chl == chr 的话
左右儿子的 suflen + prelen 合并
```

> 怎么用珂朵莉树实现？

先用`odt`维护连续的，相同字符的段，对于修改操作`str[idx] = c`，执行标准的`split`操作
将区间划分成`[l, idx-1] + [idx, idx] + [idx+1, r]`，`pl = [idx, idx], pr = [idx+1, r]`是我们要关注的段
我们尝试合并`[pl, pr)`

如果`str[idx-1] == c`，那么`[idx, idx]`和`[l, idx-1]`合并
如果`str[idx+1] == c`，那么`[idx, idx]`和`[idx+1, r]`合并，注意此时，很可能左半边已经合并过了
我们先`itl = --upper_bound(idx)`，找到左半边的段`[ll, lr, llen]`，右半边的`pr = [idx+1, r]`我们已知了
对应的段是`[rl, rr, rlen]`，新的段是`[ll, rr]`

**合并**的意思就是把旧的删除，插入一个新的`[ll, rr]`段

> 接着怎么求最大长度？

珂朵莉树的区间定义成`(l, r, v = len)`，维护的就是区间的长度，然后用一个`multiset`和`set`建立一一对应的映射关系

如果删除`it = (l, r, v)`，在`multiset`中同步删除`it->v`，插入同理

> 算法实现的坑点

1.建立一一映射的时候，注意，`split`中也有删除操作，要对应地在`multiset`中执行删除
另外，`split`操作会把`[l, r] --> [l, x-1] + [x, r]`，此时分裂出来的区间信息**不一定和原来的相同**
比如元素的个数，此时要重新计算

2.**区间修改操作**，**一开始**需要把目标区间`[l, r]`分裂出来，`multiset`本来存的是**相同的一整段**
而我们分裂出来一个`[idx, idx]`，相当于凭空多出来了一个长度为`1`的段，要把对应的段插入`multiset`中
即`multiset.insert(1)`

```bash
class Solution {
public:
    vector<int> longestRepeating(string s, string qch, vector<int>& qid) {
        int n = s.size();
        odt.clear();
        st.clear();

for (int i = 0; i < n; i++) {
            int j = i;
            while (j + 1 < n && s[j+1] == s[j]) j += 1;
            // [i, j]
            odt.insert(Node( i, j, j-i+1 )), st.insert(j-i+1);

i = j;
        }

auto calc = [&](char ch, int k) -> int {
            s[k] = ch;
            auto pr = split(k+1), pl = split(k);
            st.insert(1);

if (k - 1 >= 0 && s[k-1] == ch) {
                auto itl = --odt.upper_bound(Node(k-1, 0, 0));

odt.erase(pl), st.extract(1);
                auto [l, r, len] = *itl;
                odt.erase(itl), st.extract(len);

odt.insert(Node(l, k, k-l+1)), st.insert(k-l+1);
            }
            
            if (k + 1 < n && s[k+1] == ch) {
                // pr: [k+1...?) = [rl, rr), 
                auto itl = --odt.upper_bound(Node(k, 0, 0));

auto [rl, rr, rlen] = *pr;
                odt.erase(pr), st.extract(rlen);

auto [ll, lr, llen] = *itl;
                odt.erase(itl), st.extract(llen);

odt.insert(Node(ll, rr, rr-ll+1)), st.insert(rr-ll+1);
            }

return *st.rbegin();
        };

int m = qch.size();

vector<int> res;
        for (int i = 0; i < m; i++) {
            char ch = qch[i];
            int k = qid[i];

res.push_back(calc(ch, k));
        }

return res;
    }
};
```

### 2025 National Invitational of CCPC (Zhengzhou)
#### C
**[Toxel 与宝可梦图鉴](https://codeforces.com/gym/105941)**
**问题描述**
给定一个长度为$$n$$的序列，其中$$a_i$$表示第$$i$$个宝可梦的**编号**是$$a_i$$
现在有$$m$$次操作，每次操作用`l r d`描述，表示$$[l, r]$$中的所有数，改成$$[d, d+1, \cdots, d+r-l]$$
现在输出$$m+1$$行，每行两个数，分别表示
**交换前**，最多数量的宝可梦的**编号**，数量相同，输出$$a_i$$最小的那个
**交换后**，数量最多的宝可梦**有多少个？**（数量具体是多少？）

**算法分析**
朴素的想法是，对值域$$a_i$$建线段树，维护$$(mxcnt, mxid)$$，当且仅当`child`的`cld.mxcnt > mxcnt`的时候
更新`maxcnt = cld.mxcnt, mxid = cld.mxid`

然后每一次我们查询根节点的`(mxcnt, mxid)`就可以了

难点在于修改操作，要做两件事情
1.对于`[l, r]`中出现的所有数，可能离散在若干个不同的位置，我们要在线段树上让这些位置都`-1`
2.同时`[d, d+r-l]`执行区间加，`+= 1`，这一步比较容易处理

> 难点就是，对于`[l, r]`中出现的所有数，离散在若干位置，怎么在线段树上执行，这些位置都`-1`的操作，难不成是暴力？

但注意，这里每次操作，都是把一整段修改成`[d, d+1, d+2, ....]`，所以最后一定会形成若干个`[d, d+1, ...]`的段
即`d 开头，公差是 1 的等差数列`，`m`次均摊下来，这样的段差不多是$$\log$$级别的

于是我们可以考虑**珂朵莉树**，`odt`每次维护形如`[l, r] = [d, d+1, ..., d+len-1]`的段，用`(l, r, d)`来表示
这样`split`分离出$$[l, r]$$的段之后，每一小段`(it.l, it.r, d)`，就对应线段树上的连续的区间
执行区间修改`[d, d+(it.r-it.l)]`

遍历每个这样的小段，并在线段树上对应**区间减**，然后记得把旧的段删掉（因为要合并）
（`odt`合并就是暴力删旧的，然后加新的）

遍历之后，加入新的段`(l, r, d2)`，插入`(l, r, d2)`，并且线段树同时执行`[d2, d2+(r-l)]`区间`+1`

> 这样大致就做完了，一些细节

**怎么求出现次数最多的数是哪一个？**
上面说到，维护`mxid`，但很可惜，这样做并不对，为什么呢？
因为我们执行的是**区间修改**，**懒标记**可能并不会递归到叶子结点，递归不下去，就不会对`mxid`进行修改

一开始很可能出现次数最多的数如下，`le = [...id1...],  ri = [..+1...+1...+1]`，`id1`是出现次数最多的
但我们后续反复对区间`ri`进行修改，不断`+1`，这时候出现次数最多的数，`mxid`应该要变成`ri`中的数
很可惜没有，修改的时候，懒标记并不能动态维护**出现次数最多的数，到底是哪个？**

但是，**线段树二分**可以完美解决这个问题，线段树二分可以将懒标记递归到叶子结点，很好地完成修改
同时我们只需要在`[1, N]`中，二分最小的，值是`maxcnt`的位置，这也可以很方便地做到

#### 算法实现
```bash
// 线段树二分用
int base = 0;
bool fl(int data) {
    if (data < base) return true;
    else return false; 
}

void solve(int cas) {
    int n, m;
    cin >> n >> m;

// mxcnt, id
    int N = 2 * n;
    lazy_segtree<int, op, int, mapping, comp, id> tr(vector<int>(N+1, 0), N);
    vector<int> a(n+1, 0);

map<int, int> cnt;

for (int i = 1; i <= n; i++) {
        cin >> a[i], cnt[a[i]] += 1;
        tr.change(1, 1, N, a[i], cnt[a[i]]);
    }

// debug(tr.query(1, 1, N, 1, N).mxcnt);

// odt
    set<Node> odt;
    // odt.insert(Node(n+1, N, 0));

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

auto split = [&](int x) {
        // [l, r] -> [l, x-1] + [x, r], x 是下标，返回指向 [x, r] 的迭代器
        auto it = odt.lower_bound((Node){x, 0, 0});

if (it != odt.end() && it->l == x) return it;
        it--;

// it=[l, r] -> [l, x-1] + [x, r]
        auto [l, r, d] = *it;
        int d2 = d + (x - l);

odt.erase(it);

odt.insert(Node(l, x-1, d));
        return odt.insert(Node(x, r, d2)).first;
    };

auto oper = [&](int l, int r, int d2) -> void {
        // [l, r]
        auto itr = split(r+1), itl = split(l);

for (auto it = itl; it != itr; it++) {
            auto [cl, cr, d] = *it;
            int L = d, R = d + (cr - cl);
            tr.modify(1, 1, N, L, R, -1);
        }
        odt.erase(itl, itr);

int L = d2, R = d2 + (r - l);
        tr.modify(1, 1, N, L, R, 1);

odt.insert(Node(l, r, d2));
    };

// m oper
    auto mxcnt = tr.query(1, 1, N, 1, N);

base = mxcnt;
    auto mxid = tr.max_right<fl>(1, 1, N, 1, N);

cout << mxid << " " << mxcnt << "\n";

for (int i = 0; i < m; i++) {
        int l, r, d;
        cin >> l >> r >> d;

// change, oper(l, r+1)
        oper(l, r, d);

auto mxcnt2 = tr.query(1, 1, N, 1, N);
        base = mxcnt2;
        auto mxid2 = tr.max_right<fl>(1, 1, N, 1, N);

cout << mxid2 << " " << mxcnt2 << "\n";
    }
}
```

看完文章有啥想法

算法小站

wiki 主题

数据结构

珂朵莉树

目录