珂朵莉树的起源？

珂朵莉树原名老司机树(Old Driver Tree，ODT)，由2017年一场CF比赛中提出的数据结构，因为题目背景主角是《末日时在做什么？有没有空？可以来拯救吗？》的主角珂朵莉，因此该数据结构被称为珂朵莉树。

什么是珂朵莉树？

珂朵莉树是一种以近乎暴力的形式存储区间信息的一个数据结构。方式是通过set存放若干个用结构体表示的区间，每个区间的元素都是相同的。

珂朵莉树的用途？

只要是涉及到区间赋值操作的题，就可以用珂朵莉树处理几乎任何关于区间信息的询问

什么情况下可以用珂朵莉树而不被卡？

珂朵莉树是一种优美的暴力，他的优美是建立在区间的合并操作上，即区间赋值，那么如果构造出一组数据使得其几乎不含区间赋值操作，那珂朵莉树就会被轻易的卡掉

所以珂朵莉树要求题目必须存在区间赋值操作，且数据有高度的随机性

珂朵莉树定义

前面说过珂朵莉树是通过结构体来存储区间的，所以我们要写一个结构体

struct ran{
    int l, r;
    mutable ll v;
    bool operator <(const ran &x)const{//运算符重载,用于set的排序
        return l < x.l;//按区间的左端点从小到大来排
    }
};

什么是mutable?为什么要用mutable

mutable 关键字定义一个强制可变量

在调用函数时，往往只传参，但是函数内操作不会更改其实际的值。而珂朵莉树往往涉及需要修改v的操作，如果是一般的数据类型，我们会在变量前加上&，但对于结构体，就需要在定义时加上mutable。

set<ran>tr;//珂朵莉树的定义

set的前置知识

• 定义set：set<ran>st;

• 插入: tr.insert(ran(l, r, v));

  insetr函数其实是有返回值的，会返回一个pair<set ::iterator , bool>,第一个值是插入的元素的迭代器

• 删除

  • 删除单个元素: tr.erase(it); it是待删的元素的迭代器
  • 删除一个连续的区间的元素: tr.erase(itl, itr);，itl 和ltr是待删的区间的左右两个，左闭右开

• 二分:tr.lower_bound()，返回的是一个迭代器

• 迭代器：就是类似于数组的下标

  写起来不是很方便，所以可以使用宏定义：#define It set<ran>::iterator,使用的时候就直接It it;就行

珂朵莉的两大神器

split函数

这个函数是一个分解函数，我们要从set中的所有区间中找到pos所在的区间，拆成两个区间，一个是[l, pos - 1], 另一个是[pos, r]， 主要目的是使pos作为一个区间的开头，并返回这个区间的迭代器

It split(int pos){
    It it = tr.lower_bound({pos, -1, 0});//找到所需的pos的迭代器
    if(it != tr.end() && it->l == pos)return it;//看看这个迭代器的l是不是所需要的pos，是的话直接返回就行
    --it;//不是的话就说明肯定是在前一个里面
    int l = it->l;
    int r = it->r;
    ll v = it->v;
    tr.erase(it);//我们删掉这个区间
    tr.insert({l, pos - 1, v});//重新塞入两个区间[l, pos -1 ],[pos, r]
    return tr.insert({pos, r, v}).first;//返回以pos开头的区间的迭代器
}

emerge函数

如果不断进行split函数，会使的set的元素数量在一个很高的范围，就会导致TLE，所以我们需要一个区间合并操作，也就是针对区间赋值的一个操作

void emerge(int l, int r, ll x){
    It itr = split(r + 1), itl = split(l);//先找到r+1的迭代器位置，再找l的迭代器位置
    tr.erase(itl, itr);//删掉这一段迭代器
    tr.insert({l, r, x});//重新插入所需区间
}

你可以会疑问为什么要找r + 1，这是因为set删除的时候传参是左闭右开的，所以要删[l, r]的所有的区间，itr就应该指向r+1

E. Physical Education Lessons

题目描述：

从现在到学期结束还有 n 天(从 1到 n 编号)，他们一开始都是工作日。接下来学校的工作人员会依次发出 q 个指令，每个指令可以用三个参数 l,r,k描述：

• 如果 k=1，那么从 l 到 r （包含端点）的所有日子都变成非工作日。
• 如果 k=2，那么从 l 到 r （包含端点）的所有日子都变成工作日。

帮助Alex统计每个指令下发后，剩余的工作日天数。

思路：

珂朵莉板子题，只需要用ans实时统计答案的贡献即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;

struct ran{
    int l, r;
    mutable int v;
    ran(int L, int R = -1, bool V = 0){
        l = L;r = R;v = V;
    };
    bool operator <(const ran &x)const{
        return l < x.l;
    }
};
#define It set<ran>::iterator
set<ran>tr;
ll ans;
It split(int pos){
    It it = tr.lower_bound(ran(pos));
    if(it != tr.end() && it->l == pos)return it;
    --it;
    int l = it->l;
    int r = it->r;
    int v = it->v;
    tr.erase(it);
    tr.insert(ran(l, pos - 1, v));
    return tr.insert(ran(pos, r, v)).first;
}
void emerge(int l, int r, int v){
    It itr = split(r + 1);
    It itl = split(l);
    It it = itl;
    for(;it != itr;++it){
        ans -= it->v * (it->r - it->l + 1);
    }
    tr.erase(itl, itr);
    tr.insert(ran(l, r, v));
    ans += (r - l + 1) * v;
}


void work(){
    cin >> n >> m;
    ans = n;
    tr.insert(ran(1, n, 1));
    for(int i = 1; i <= m; ++i){
        int l, r, v;
        cin >> l >> r >> v;
        emerge(l, r, v - 1);
        cout << ans << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

C. Willem, Chtholly and Seniorious

题目描述：

请你写一种奇怪的数据结构，支持：

• 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次方的和模y的值

此外数据需要根据seed手动生成

思路：

这个题就是珂朵莉树的起源题

操作1、3、4就纯暴力就行，操作2就是珂朵莉的合并区间操作

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define It set<ran>::iterator
typedef long long ll;
typedef pair <ll,ll> pii;

#define MAX 300000 + 50
int n, m;
ll mod;
ll ar[MAX];
int op, l, r;
ll x;
struct ran{
    int l, r;
    mutable ll v;
    bool operator <(const ran &x)const{
        return l < x.l;
    }
};

set<ran>tr;
It split(int pos){
    It it = tr.lower_bound({pos, -1, 0});
    if(it != tr.end() && it->l == pos)return it;
    --it;
    int l = it->l;
    int r = it->r;
    ll v = it->v;
    tr.erase(it);
    tr.insert({l, pos - 1, v});
    return tr.insert({pos, r, v}).first;
}

void emerge_add(int l, int r, ll x = 1){
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl)itl->v += x;
}

void emerge_bian(int l, int r, ll x = 0){
    It itr = split(r + 1), itl = split(l);
    tr.erase(itl, itr);
    tr.insert({l, r, x});
}

ll get_rank(int l, int r, ll rkn){
    vector<pii>v;
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl)v.push_back(m_p(itl->v, itl->r - itl->l + 1));
    sort(v.begin(), v.end());
    for(auto [vv, len] : v){
        rkn -= len;
        if(rkn <= 0)return vv;
    }
    return 0;
}

ll q_pow(ll a, ll b, ll mod){
    ll ans = 1;
    a %= mod;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

ll get_ans(int l, int r, ll x, ll mod){
    ll ans = 0;
    It itr = split(r + 1), itl = split(l);
    for(;itl != itr;++itl){
        ans = (ans + ((ll)(itl->r - itl->l + 1) * q_pow(itl->v, (ll)x, mod)) % mod) % mod;
    }
    return ans;
}


ll seed, vmax;
ll rnd(){
    ll ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}

void work(){
    cin >> n >> m >> seed >> vmax;
    for(int i = 1; i <= n; ++i){
//        cin >> ar[i];
        ar[i] = (rnd() % vmax) + 1;
        tr.insert({i, i, ar[i]});
    }
    tr.insert({n+1, n+1, 0});
    for(int i = 1; i <= m; ++i){
//        for(auto [l, r, v] : tr){
//            cout << l << ' ' << r << ' '<< v << endl;
//        }
//        cout << endl << endl;
        op = (int)(rnd() % 4) + 1;
        l = (int)(rnd() % n) + 1;
        r = (int)(rnd() % n) + 1;
        if(l > r)swap(l, r);
        if(op == 3)x = (int)(rnd() % (r - l + 1)) + 1;
        else x = (int)(rnd() % vmax) + 1;
//        cin >> op >> l >> r >> x;
        if(op == 1){
            emerge_add(l, r, x);
        }
        else if(op == 2){
            emerge_bian(l, r, x);
        }
        else if(op == 3){
            cout << get_rank(l, r, x) << endl;
        }
        else {
//            cin >> mod;
            mod = rnd() % vmax + 1;
            cout << get_ans(l, r, x, mod) << endl;
        }
    }
    
}


int main(){
    work();
    return 0;
}