珂朵莉树

简介

珂朵莉树（Chtholly Tree）起源于 CF896Chttps://codeforces.com/problemset/problem/896/C

可以较快地实现:

• 区间加
• 区间赋值
• 求区间第k大值
• 求区间n次方和

珂朵莉树的适用范围: 有 区间赋值 操作且 数据随机 的题目

实现

珂朵莉树的思想在于: 随机数据下的区间赋值操作很可能让大量元素变为同一个数

所以, 我们以 三元组<l, r, v> 的形式保存数据(区间 $[l, r]$ 中的元素的值都是 $v$):

例如, 存在如下数组:

\[1, 2, 2, 2, 3, 3, 4\]

可以表示为:

\[<1, 1, 1>, <2, 4, 2>, <5, 6, 3>, <7, 7, 4>\]

翻译成代码表示:

struct node
{
    long long l, r;
    // mutable: 使得当整个结构体为const时, 标为mutable的成员仍可变
    mutable long long v;

    // 构造函数
    node(long long l, long long r, long long v): l(l), r(r), v(v) {}

    // 重载 `<` 操作符
    bool operator<(const node & o) const {
        return l < o.l;
    }
};

然后, 将三元组存储到 set 里:

set<node> odt;

1. 把结构体放进 set 里需要重载小于操作符, set 会保证内部元素有序(插入, 删除和查询的时间复杂度都是 $O(\log n)$)
2. mutable 使得当整个结构体为const时, 标为mutable的成员仍可变(可能有区间加操作)

区间断开操作

进行区间操作时可能会把原本连续的区间断开, 将 <l, r, v> 拆开成 l, pos - 1, v 和 pos, r, v

auto split(long long pos)
{
    // 寻找: 左端点大于等于pos的第一个节点
    auto it = odt.lower_bound(node(pos, 0, 0));

    // 已经存在以pos为左端点的节点, 直接返回
    if (it != odt.end() && it -> l == pos)
    {
        return it;
    }

    // 删除旧的节点
    it--;
    long long l = it -> l, r = it -> r, v = it -> v;
    odt.erase(it);

    // 插入新的节点
    odt.insert(node(l, pos - 1, v));

    // 返回以pos为开头的节点的迭代器
    return odt.insert(node(pos, r, v)).first;
}

区间赋值

珂朵莉树的精髓在于 区间赋值, 写法很简单:

void assign(long long l, long long r, long long v)
{
    // 首先将 区间[l, r] 范围内的节点拆开, 然后删掉
    auto end = split(r + 1), begin = split(l);
    odt.erase(begin, end);

    // 插入新的节点区间
    odt.insert(node(l, r, v));
}

使用 split() 时, 顺序 不能颠倒, 因为 split(end) 可能把 begin 原来的节点断开

区间加

暴力一点, 直接加

void add(long long l, long long r, long long v)
{
    auto end = split(r + 1);

    for (auto it = split(l); it != end; it++)
    {
        it -> v += v;
    }
}

区间第k大值

long long kth(long long l, long long r, long long k)
{
    auto end = split(r + 1);

    // pair: 存节点的值和区间长度
    vector<pair<long long, long long>> v;
    for (auto it = split(l); it != end; it++)
    {
        v.emplace_back(make_pair(it -> v, it -> r - it -> l + 1));
    }
    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++)
    {
        k -= v[i].second;
        if (k <= 0)
        {
            return v[i].first;
        }
    }
}

区间n次方和

long long qpow(long long a, long long n, long long mod)
{
    long long ans = 1;
    a %= mod;

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

    return ans;
}

long long sum_of_pow(long long l, long long r, long long x, long long y)
{
    long long ans = 0;
    auto end = split(r + 1);

    for (auto it = split(l); it != end; it++)
    {
        ans = (ans + qpow(it -> v, x, y) * (it -> r - it -> l + 1)) % y;
    }

    return ans;
}