【数据结构】ODT(珂朵莉树)

前言

多学一点数据结构一般是有好处的，至少可以帮你打暴力
——Wei_taming

因此，作者开始补习DL数据结构

---

什么是珂朵莉？

珂朵莉是世界上最幸福的女孩子，没有之一，不接受任何反驳！

---

什么是珂朵莉树？

珂朵莉树原名ODT(Ord Driver Tree)，即老司机树。是一种基于set的暴力数据结构，起源于Codeforces-896C

其原理在于使用STL中的set来维护一段连续的相同元素。

它的时间复杂度其实是假的，但在数据随机时可以有很好的表现。

而且珂朵莉树使用的局限性较大，如果没有区间赋值操作，则珂朵莉树就毫无用武之地。

因此，珂朵莉树大部分情况用于骗分。

---

珂朵莉树的核心操作

定义节点

#define ll long long

struct Node{
    int l , r;
    mutable ll val;
    bool operator < (const Node & b) const{
        return l < b.l
    }
};

set<Node > S;

在上面的代码中，每一个Node都是在维护一段连续的区间，这些区间的大小不等。

其中，$l$代表区间左端点，$r$代表区间右端点，$val$代表当前这段区间每一个元素的值.

顺带提一句，mutable可以直接对迭代器进行修改而不影响里边的值。

最后重载运算符，调整每一个节点在set中的存储顺序。

这样，我们就完成了珂朵莉树的节点创建。

---

建树

对于建树，我们只需要把区间中的每一个数看做一段长度为$1$的区间，然后暴力插入即可

Code

ll a[10001];

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

---

分裂(Spilt)

$Spilt(pos)$操作可以将含有$pos$位置的区间分为两部分，分别为$[1 , pos - 1]$与$[pos , r]$

Code

#define range set<Node > S :: iterator

range spilt(int pos){
    range it = S.lower_bound((Node){pos , pos , -1});
    if(it != S.end() && it -> l == pos){
        return it;
    }
    it --;
    Node ins = *it;
    S.erase(it);
    S.insert((Node){ins.l , pos - 1 , ins.val});
    return S.insert((Node){pos , ins.r , ins.val}).first;
}

上面的函数的返回值为一个迭代器，代表从$[pos , r]$这一段区间，方便之后的操作。

在函数的开头，我们需要寻找第一个左端点$l$大于等于$pos$的节点。

之后对其进行特判：如果说找到的这段区间不在珂朵莉树的末尾，而且找到的这个节点的$l = pos$,则证明我们找到了这个节点，直接返回即可。

否则，则刚刚找到的这个节点的$l$一定大于$pos$（我们使用的是lower_bound，找到的那段区间的$l$一定大于等于$pos$，而等于的情况已经被我们特判掉）。因此我们需要返回到上一段区间进行寻找。

之后需要一个替代变量$ins$存储我们刚刚找到的区间，然后将原来的的区间删掉，再插入$[l , pos - 1]$与$[pos , r]$，最后返回以$pos$为左端点$l$的区间，即$[pos , r]$。

现在，我们就完成了珂朵莉树的分裂操作。

---

区间推平(Assign)

现在，我们已经可以轻松分裂一颗珂朵莉树。

但随着珂朵莉树的不断分裂，set中的元素也会渐渐增多，从而不断增大珂朵莉树的时间复杂度。

因此，我们还需要$Assign$来降低时间复杂度。

$Assign$操作的用处在于推平一段区间，说白了，就是将一个区间全部修改为一个值，从而合并珂朵莉树。

在数据随机的情况下，$Assign$操作的出现频率并不小，大约在$\frac{1}{3}$上下。而且$Assign$操作可以一次合并多个节点，可以将set的大小控制在一个可控的范围之内。因此，$Assign$操作是珂朵莉树的重要保证。

Code

void assign(int l  , int r , ll val){
    range R = spilt(r + 1);         
    range L = spilt(l);     
    S.erase(L , R);
    S.insert(Node{l , r , val});
}

首先，我们分别分裂左右区间。(要注意，这里需要先分裂右区间。因为在分离左区间时会导致迭代器失效，若这时强行分裂，会导致程序$RE$)

之后我们分别删除我们分离出来的左右区间，最后将整段区间加入即可。

---

珂朵莉树的其他操作

下面我们就以珂朵莉树的起源:Codeforces-896C为例，讲解珂朵莉树的其他操作。

区间加

直接分裂出区间端点，然后暴力解决即可

void range_add(int l , int r , int val){
    range R = spilt(r + 1);
    range L = spilt(l);
    for(range i = L; i != R; i ++){
        i -> val += val;
    }
}

---

区间快速幂之和

即求：$\sum_{i = 1}^{r} a^x_i$

对每一段区间暴力快速幂即可。

ll Pow(ll a , ll n , ll HA){
    if(n == 0){
        return 1;
    }
    if(n == 1){
        return a % HA;
    }
    ll c = Pow(a , n / 2 , HA);
    if(n % 2 == 0){
        return c * c % HA;
    }
    else{
        return (c * c * a) % HA;
    }
}

ll range_pow(int l , int r , ll val , ll HA){
    range R = spilt(r + 1);
    range L = spilt(l);
    ll ans = 0;
    for(range i = L; i != R; i ++){
        ans += (ll)(i -> r - i -> l + 1) * Pow(i -> v , val , HA);
        ans %= HA;
    }
    return ans;
}

---

区间第k大

原理也很简单，就是把那段区间的元素丢入一个vector，然后排序。

ll range_query(int l , int r , int k){
    #define pairs pair<ll , int>

    vector<pairs > V;
    V.clear();
    range R = spilt(r + 1);
    range L = spilt(l);
    for(range i = L; i != R; i ++){
        V.push_back(pairs(i -> val , i -> r - i -> l + 1));
    } 
    sort(V.begin() , V.end());
    ll sum = 0;
    for(vector<pairs > :: iterator i = V.begin(); i != V.end(); i ++){
        sum += i -> second;
        if(sum >= k){
            return i -> first;
        }
    }
    return -1;
}

---

操作模板

不知道大家看出来了没有，珂朵莉树的操作大部分是有模板可以套的。

模板如下

void change(int l , int r , int val){
    range R = spilt(r + 1);
    range L = spilt(l);
    for(range i = L; i != R; i ++){
        ………………
    }
}

---

Code[Ctholly Tree]

最后放上珂朵莉树起源的代码好了（为啥我觉得一半代码都在写数据生成器？？？）

题目链接:Codeforces-896C

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<set>

#define ll long long
#define I inline
#define N 100001

using namespace std;

int n , m , s;
int a[N];

namespace ODT{
    #define range set<Node> :: iterator

    struct Node{
        int l , r;
        mutable ll val;
        bool operator < (const Node &b) const{
            return l < b.l;
        }
    };                       

    set<Node > S; 

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

    range spilt(int pos){
        range it = S.lower_bound((Node){pos , pos , -1});
        if(it != S.end() && it -> l == pos){
            return it;
        }
        it --;
        Node ins = *it;
        S.erase(it);
        S.insert((Node){ins.l , pos - 1 , ins.val});
        return S.insert((Node){pos , ins.r , ins.val}).first;
    }

    void assign(int l  , int r , ll val){
        range R = spilt(r + 1);
        range L = spilt(l);
        S.erase(L , R);
        S.insert(Node{l , r , val});
    }

    void range_add(int l , int r , int val){
        range R = spilt(r + 1);
        range L = spilt(l);
        for(range i = L; i != R; i ++){
            i -> val += val;
        }
    }

    ll Pow(ll a , ll n , ll HA){
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return a % HA;
        }
        ll c = Pow(a , n / 2 , HA) % HA;
        if(n % 2 == 0){
            return (c * c) % HA;
        }
        else{
            return  (((c * c) % HA) * a) % HA;
        }
    }

    ll range_pow(int l , int r , ll val , ll HA){
        range R = spilt(r + 1);
        range L = spilt(l);
        ll ans = 0;
        for(range i = L; i != R; i ++){
            ans += (ll)(i -> r - i -> l + 1) * Pow(i -> val , val , HA);
            ans %= HA;
        }
        return ans;
    }

    ll range_query(int l , int r , int k){
        #define pairs pair<ll , int>

        vector<pairs > V;
        V.clear();
        range R = spilt(r + 1);
        range L = spilt(l);
        for(range i = L; i != R; i ++){
            V.push_back(pairs(i -> val , i -> r - i -> l + 1));
        } 
        sort(V.begin() , V.end());
        ll sum = 0;
        for(vector<pairs > :: iterator i = V.begin(); i != V.end(); i ++){
            sum += i -> second;
            if(sum >= k){
                return i -> first;
            }
        }
        return -1;
    }
}

ll seed, vmax;

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

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

    cin >> n >> m >> seed >> vmax;
    for (ll i = 1; i <= n; i ++){
        ODT::S.insert(ODT :: Node{i, i, (rnd() % vmax) + 1});
    }
    ll x, y;
    while (m --){
        x = 0, y = 0;
        ll op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1;
        if (l > r){
            swap(l , r);
        }
        if (op == 3){
            x = (rnd() %(r - l + 1)) + 1;
        }
        else{
            x = (rnd() % vmax) + 1;
        }
        if (op == 4){
            y = (rnd() % vmax) + 1;
        }
        switch (op){
            case 1:
                ODT :: range_add(l, r, x);
                break;
            case 2:
                ODT :: assign(l, r, x);
                break;

            case 3:
                cout << ODT :: range_query(l, r, x) << endl;
                break;

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

---

THE END