珂朵莉树（ODT）详解

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

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

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

珂朵莉树の前世今生

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

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

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

珂朵莉树简介

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

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

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

• 例如：

珂朵莉树是这样存的：

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;
}