前言

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

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


什么是珂朵莉?

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

Chtholly.png


什么是珂朵莉树?

珂朵莉树原名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;
}
}

区间快速幂之和

即求:

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

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