珂朵莉树(ODT)详解

发布于 2019-10-04  320 次阅读


こんなにも、たくさんの幸せをあの人に分けてもらった
だから、きっと
今の、私は
誰が何と言おうと

「うん。梦も叶ったし、いい思い出もできたし、思い残すことはもうないかな」

珂朵莉树保持复杂度主要依靠assign操作,所以题目中必须有区间赋值

还有很重要的一点:数据需纯随机

数据随机很重要,因为如果推平区间操作很少 / 很多单点,珂朵莉会被卡掉呀QwQ

珂朵莉树の前世今生

珂朵莉树又名ODT(Old Driver Tree)

因为珂朵莉树又名老司机树,所以珂朵莉 = 老司机
___Payphone—X

在CF896C Willem, Chtholly and Seniorious中,她首次问世,作为一个非标程的数据结构,她拥有可以吊打标程的速度。

珂朵莉树简介

珂朵莉树是一个十分暴力的数据结构,可以对区间进行修改,她有多暴力?她除了区间推平(即区间集体赋值)是板子之外,其余的全靠for O(n) 求。

她是用来维护一个STL set的,也就是对set进行各种骚操作,因为set是红黑树实现的,所以您如果够强,您也可以手写红黑树。

珂朵莉树的每一个节点和线段树一样,是存储一段区间的信息,不过与之不同的是,珂朵莉树的节点只存相同的元素。

  • 例如:
区间 p1 p2 p3 p4 p5 p6 p7 p8 p9
5 5 5 1 2 8 8 8 7

珂朵莉树是这样存的:

  1. (p1 到 p3 的值全是5)
  2. (p4 到 p4 的值全是1)
  3. (p5 到 p5 的值全是2)
  4. (p6 到 p8 的值全是8)
  5. (p9 到 p9 的值全是7)

就这样存完了

珂朵莉树の基本操作

存储结构

珂朵莉树因为要用到set,并对它进行骚操作,所以不可避免地要碰到指针和迭代器和毒瘤码风。

以下是结构体:

struct node
{
    int l, r;   //区间左端点l,和右端点r
    mutable long long val;  //区间的值
    node(long long ll, long long rr = -1, LL vv = 0) //构造函数(定义临时节点或赋值用)
    {
        l = ll, r = rr, val = vv;
    }
    bool operator<(const node &b) const //运算符重载
    {
        return l < b.l;
    }
};

set<node> s;

这里来解释一下什么是mutable.

mutable 是用来修饰一个 const 示例的部分可变的数据成员的。如果要说得更清晰一点,就是说 mutable 的出现,将 C++ 中的 const 的概念分成了两种。

二进制层面的 const,也就是「绝对的」常量,在任何情况下都不可修改(除非用 const_cast)。

引入 mutable 之后,C++ 可以有逻辑层面的 const,也就是对一个常量实例来说,从外部观察,它是常量而不可修改;但是内部可以有非常量的状态。
当然,所谓的「逻辑 const」,在 C++ 标准中并没有这一称呼。这只是为了方便理解,而创造出来的名词。

显而易见,mutable 只能用来修饰类的数据成员;而被 mutable 修饰的数据成员,可以在 const 成员函数中修改。

也就是说,只要定义了,mutable类型,加上迭代器,我们就可以不通过insert,push等操作修改set内部的元素,可以直接使用类似数组修改的办法修改set中的值辣!

珂朵莉树の返回“下标"(指针)操作

我们假如要修改一段区间,而这段区间不可能正好在珂朵莉树的一个节点上,这要怎么办呢,这时后我们要写一个函数split(pos),把节点拆开,拆成l~pos-1,pos~r。

举个栗子理解一下:这里用(l,r,val)来表示一个节点

设原节点按照set的排序顺序为(1,2,1), (3,6,2), (7,7,3)

那么split(5)操作后的节点序列就变为(1,2,1), (3,4,2), (5,6,2), (7,7,3)

#define IT set<chtholly>::iterator // (1)

inline IT split(int pos)
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && pos == it->l)
        return it;
    --it;   // (2)
    int L = it->l, R = it->r; 
    long long val = it->val;
    s.erase(it);         //删除原节点
    s.insert(node(L, pos - 1, val));  //分裂原节点
    return s.insert(node(pos, R, val)).first; //返回pos~r点的指针
}

这里返回的是代表[pos,r]区间的节点的迭代器,方便于其他操作。

  • (1): emmmmm,这就是传说中的STL迭代器了,没了他你就不能访问STL容器中的内部元素了。

  • (2): 这里的lower_bound不是普通的二分查找,他返回第一个不小于pos的l,也就是说l<=pos,所以要么it是set的右端点,要么pos恰好等于l,否则由于lower_bound返回第一个不小于pos的l,所以pos所在位置的指针一定在l后面,令it--即可。

珂朵莉树の推平操作

这个非常简单啦,就短短几行代码。

inline void assign(long long l, long long r, long long x)
{
    IT itr = split(r + 1), itl = split(l);
    tree.erase(itl, itr);   //删掉这俩区间
    tree.insert(node(l, r, x));  //新建一个
}

为什么要先split出r+1呢?

因为如果先split出l,再split出r+1,之前的itl可能就不是l对应的迭代器了。

珂朵莉树の其他暴力操作

  • 以CF897C举例,大家自己体会体会有多暴力。

区间加

暴力一个个加

inline void add(long long l, long long r, long long x)
{
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++)
        it->val += x;
}

区间第k小

暴力取出后排序

inline long long k_small(long long l, long long r, long long x)
{
    vector<pair<LL, int>> a;
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++)
        a.push_back(pair<LL, int>(it->val, it->r - it->l + 1));
    sort(a.begin(), a.end());
    for (vector<pair<LL, int>>::iterator it = a.begin(); it != a.end(); it++)
    {
        x -= it->second;
        if (x <= 0)
            return it->first;
    }
}

珂朵莉树暴力通用模板

void performance(int l, int r) {
  IT itr = split(r + 1), itl = split(l);
  for (IT it = itl; it != itr; it++) {
    // Perform Operations here
  }
}

CF896C code

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#define IT set<chtholly>::iterator //方便写代码
#define maxn 10000
#define mod %
typedef long long LL;
using namespace std;

namespace chthollyTree
{

struct chtholly
{
    long long l, r;
    mutable long long val;
    chtholly(long long ll, long long rr = -1, LL vv = 0) //构造函数(定义临时节点或赋值用)
    {
        l = ll, r = rr, val = vv;
    }
    bool operator<(const chtholly &b) const //运算符重载
    {
        return l < b.l;
    }
};

set<chtholly> tree;

inline IT split(long long pos)
{
    IT it = tree.lower_bound(chtholly(pos));
    if (it != tree.end() && pos == it->l)
        return it;
    --it;
    long long L = it->l, R = it->r;
    LL val = it->val;
    tree.erase(it);
    tree.insert(chtholly(L, pos - 1, val));
    return tree.insert(chtholly(pos, R, val)).first;
}

inline void assign(long long l, long long r, long long x)
{
    IT itr = split(r + 1), itl = split(l);
    tree.erase(itl, itr);
    tree.insert(chtholly(l, r, x));
}

inline void add(long long l, long long r, long long x)
{
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++)
        it->val += x;
}

inline long long k_small(long long l, long long r, long long x)
{
    vector<pair<LL, int>> a;
    IT itr = split(r + 1), itl = split(l);
    for (IT it = itl; it != itr; it++)
        a.push_back(pair<LL, int>(it->val, it->r - it->l + 1));
    sort(a.begin(), a.end());
    for (vector<pair<LL, int>>::iterator it = a.begin(); it != a.end(); it++)
    {
        x -= it->second;
        if (x <= 0)
            return it->first;
    }
}

inline LL qpow(LL x, long long y, long long m)
{
    LL ans = 1;
    x = x % m;
    while (y)
    {
        if (y & 1)
            ans = ans * x % m;
        x = x * x % m;
        y >>= 1;
    }
    return ans;
}

inline LL pow(long long l, long long r, long long x, long long y)
{
    IT itr = split(r + 1), itl = split(l);
    long long ans = 0;
    for (IT it = itl; it != itr; it++)
        ans = ((ans + (LL)(it->r - it->l + 1) * qpow(it->val, (LL)x, (LL)y)) % y + y) % y;
    return ans;
}

} // namespace chthollyTree
using namespace std;
LL n, m, seed, vmax;

inline LL rnd()
{
    LL ret = seed;
    seed = (seed * 7 + 13) mod 1000000007;
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> seed >> vmax;

    for (long long i = 1; i <= n; i++)
        chthollyTree::tree.insert(chthollyTree::chtholly(i, i, (rnd() % vmax) + 1));

    long long x, y;

    while (m--)
    {
        x = 0, y = 0;
        long long op = (rnd() mod 4) + 1, l = (rnd() mod n) + 1, r = (rnd() mod n) + 1;
        if (l > r)
            swap(l, r);

        if (op == 3)
            x = (rnd() mod(r - l + 1)) + 1;
        else
            x = (rnd() mod vmax) + 1;

        if (op == 4)
            y = (rnd() mod vmax) + 1;
        switch (op)
        {
        case 1:
            chthollyTree::add(l, r, x);
            break;
        case 2:
            chthollyTree::assign(l, r, x);
            break;

        case 3:
            cout << chthollyTree::k_small(l, r, x) << endl;
            break;

        case 4:
            cout << chthollyTree::pow(l, r, x, y) << endl;
            break;
        }
    }
    return 0;
}