Ⅰ 什么是珂朵莉?

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

Ⅱ 什么是珂朵莉树?

珂朵莉树又称ODT,是一种基于$std::set$ 的数据结构,复杂度其实是假的,但是在数据随机的时候可以有很好的表现。

但是珂朵莉树的使用局限性较大,非常好卡,而且如果没有区间赋值操作的话,那就是毫无用武之地。

说白了就是用$set$维护一段连续的相同元素。

Ⅲ 珂朵莉树的实现

1.定义节点

1
2
3
4
5
6
7
8
9
struct Node{
int l;
int r;
mutable ll v;
bool operator < (const Node &b) const {
return l < b.l;
}
};
std::set<Node> s;

我来解释一下各部分吧。

$l, r$很显然就是这个区间的左右端点。

$v$很显然就是这个区间共同的权值。

顺便说一下$mutable$,这是个黑科技,可以让你对着迭代器直接修改里面不影响顺序的值。

然后下面那个重载运算符就是拿来为了让它在$set$里面的顺序是对的。

哦对,为了方便,我一般习惯加上这么一句:

1
#define iter std::set<Node>::iterator

看后面代码的时候自行脑补一下吧QwQ

2.建树

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

应该不用我多讲,就是把每个点当做一个连续的段暴力插入就行了。

3.核心操作1 $split$

$split$操作,顾名思义,就是把原来一段的一个区间分成两段。

一般而言,$split$操作都要返回切成的两块区间的右边那段的$iterator$。

1
2
3
4
5
6
7
8
9
10
iter split(int pos){
iter it = s.lower_bound((Node){pos, pos, -1}); // 找到它的后一个
if (it != s.end() && it->l == pos) // 如果根本无需删除,直接return
return it;
it--; // 因为找到的是我们需要split的后一个,所以应当分离
Node ins = *it; // 先把我们要删掉的节点存储好
s.erase(it); // 分离 = 删除 + 2 * 插入
s.insert((Node){ins.l, pos - 1, ins.v});
return s.insert((Node){pos, ins.r, ins.v}).first;
}

个人认为注释里面应该写的比较清楚了QwQ

这应该是最难懂的部分了,如果这部分看懂了接下来的就不难了。

4.核心操作2 $assign$

$assign$操作虽然有个很好听的名字:推平一段区间

但是实际上,就是个区间赋值。

那为什么说$assign$操作也是珂朵莉树的核心操作呢?

因为珂朵莉树的复杂度是由它保证的。

一次$assign$操作就会是$set$的规模大幅度减少,而且保证数据随机的情况下,$assign$操作出现的概率不小,而且一次的范围也很大,会让$set$的规模一直在一个很小的范围里。(毕竟人家$split$一次才多一个,$assign$一下直接一段区间就推平了)

给上代码~

1
2
3
4
5
6
void assign(int l, int r, ll v){
iter it_r = split(r + 1);
iter it_l = split(l);
s.erase(it_l, it_r); // 这样子就可以erase一个区间了
s.insert((Node){l, r, v});
}

特别短小精悍有木有?

其他常用操作

我们这边就以珂朵莉树公认模板题$Willem, Chtholly\ and\ Seniorious$来做例子了

原题传送门:>Here<

5.区间加

暴力加。

把两端$split$出来,然后,把中间的所有$iterator$里的$v$全都加上$c$。

然后我们之前假的$mutable$标记就可以用上了(

1
2
3
4
5
6
7
void modify(ll l, ll r, ll c){
iter it_r = split(r + 1);
iter it_l = split(l);

for(iter it = it_l; it != it_r; it++)
it->v += c;
}

又一个一个for循环解决的操作

接下来的操作就可以体现出珂朵莉树的强大了。

6.求$\displaystyle\sum_{i = l}^{r} a_i^x$

1
2
3
4
5
6
7
8
9
10
ll query(int l, int r, ll x, ll y){
iter it_l = split(l);
iter it_r = split(r + 1);
ll ans = 0;
for(iter it = it_l; it != it_r; it++){
ans += (ll)(it->r - it->l + 1) * powmod(it->v, x, y);
ans %= y;
}
return ans;
}

快速幂大家应该都会,应该不会有人没学快速幂就来学这种DL数据结构吧,我就不贴了。

恩,就是这么暴力,把每段区间取出来,把每个元素的$x$次方算出来,乘上这个连续段的长度,加起来,显然就是答案了。

7.区间第k大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Node2{
ll len;
ll v;
};
bool cmp(Node2 a, Node2 b){
return a.v < b.v;
}

ll k_query(ll l, ll r, ll k){
std::vector<Node2> q;
q.clear();
iter it_l = split(l);
iter it_r = split(r + 1);
for(iter it = it_l; it != it_r; it++)
q.push_back((Node2){it->r - it->l + 1, it->v});
std::sort(q.begin(), q.end(), cmp);
ll sum = 0;
for(std::vector<Node2>::iterator it = q.begin(); it != q.end(); it++){
sum += it->len;
if(sum >= k)
return it->v;
}
return -1;
}

这个稍微复杂一点,但是实际上还是暴力。

把所有元素取出来,记录一下每个元素出现的数量。

然后把元素排个序,就可以愉快的找到第$k$大了。

至此,$CF896C$的所有操作都讲完了。

这边我顺便贴一下$CF896C$的完整代码把

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define iter std::set<Node>::iterator

ll n, m;
ll seed, vmax;

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

struct Node{
ll l;
ll r;
mutable ll v;
bool operator < (const Node &b) const {
return l < b.l;
}
};
std::set<Node> s;

iter split(ll pos){
iter 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.v});
return s.insert((Node){pos, ins.r, ins.v}).first;
}

void assign(ll l, ll r, ll v){
iter it_l = split(l), it_r = split(r + 1);
s.erase(it_l, it_r);
s.insert((Node){l, r, v});
}

ll powmod(ll a, ll b, ll mod){
a %= mod;
ll sum = 1;
while(b){
if(b & 1){
sum *= a;
sum %= mod;
}
a *= a;
a %= mod;
b >>= 1;
}
return sum;
}

ll query(ll l, ll r, ll x, ll y){
iter it_l = split(l);
iter it_r = split(r + 1);
ll ans = 0;
for(iter it = it_l; it != it_r; it++){
// prllf("[%d %d] -> %d\n", it->l, it->r, it->v);
ans += (ll)(it->r - it->l + 1) * powmod(it->v, x, y);
ans %= y;
}
return ans;
}

void modify(ll l, ll r, ll c){
iter it_l = split(l);
iter it_r = split(r + 1);

for(iter it = it_l; it != it_r; it++){
// Node ins = *it;
// ins.v += c;
// s.erase(it);
// s.insert(ins);
// it = s.find(ins);
it->v += c;
}
}

struct Node2{
ll len;
ll v;
};
bool cmp(Node2 a, Node2 b){
return a.v < b.v;
}

ll k_query(ll l, ll r, ll k){
std::vector<Node2> q;
q.clear();
iter it_l = split(l);
iter it_r = split(r + 1);
for(iter it = it_l; it != it_r; it++)
q.push_back((Node2){it->r - it->l + 1, it->v});
std::sort(q.begin(), q.end(), cmp);
ll sum = 0;
for(std::vector<Node2>::iterator it = q.begin(); it != q.end(); it++){
sum += it->len;
if(sum >= k)
return it->v;
}
return -1;
}

ll a[100010];

int main(){
std::cin >> n >> m >> seed >> vmax;
for(ll i = 1; i <= n; i++)
a[i] = rnd() % vmax + 1;
for(int i = 1; i <= n; i++)
s.insert((Node){i, i, a[i]});
s.insert((Node){n + 1, n + 1, 0});
int cnt = 0;
for(ll i = 1; i <= m; i++){
ll type = (rnd() % 4) + 1;
ll l = (rnd() % n) + 1;
ll r = (rnd() % n) + 1;
ll x, y;

if(l > r)
std::swap(l, r);
if(type == 3)
x = (rnd() % (r - l + 1)) + 1;
else
x = (rnd() % vmax) + 1;
if(type == 4)
y = (rnd() % vmax) + 1;

if(type == 1){
modify(l, r, x);
} else if(type == 2){
assign(l, r, x);
} else if(type == 3){
printf("%I64d\n", k_query(l, r, x));
cnt++;
} else if(type == 4){
printf("%I64d\n", query(l, r, x, y));
cnt++;
}
}
}

为什么感觉一大半代码都是随机数生成器的

Ⅳ 可以使用珂朵莉树的其他题目

例题1

给定一个仅包含小写字母的字符串。

资瓷区间排序

求$m$次排序之后的字符串。

这题的正常做法是线段树维护一个桶,然后在排序的时候进行26次的查询与修改。

这样的话虽然理论复杂度是$O(n \log n)$的,但是带一个$26$的大常数,极易造成卡常。

如果使用珂朵莉树的话,我们可以用类似这种线段树的做法,查询每个字母出现的数量,再进行26次区间修改操作。

于是我们可以发现,一次排序之后,这一段区间最后只会被分成$26$个$set$中元素,规模完全可以接受。

实测在数据随机的情况下,珂朵莉树暴打$O(n \log * 26)$的标算。

(这是我们某次模拟赛的题目)

(结果标算T飞了,时限开到7s都拯救不了,而某位dalao同学spfa使用珂朵莉树A了,A了就算了,还快的飞起,于是该同学之后不久改名叫做Chtholly_Tree,并留下一句名言:)

模拟赛使我相信珂学。

例题2

>Here<

一个长度为$10^9$的0-1串,初始值全为$1$

资瓷区间修改为0或者为1

求每次修改之后$1$的个数。

这道题目正统做法是动态开点线段树。

但是显然区间修改让我们往珂朵莉树方面去想

我们只需要让珂朵莉树资瓷$assign$还有区间求和就行了

Ⅴ 总结-珂朵莉树的优缺点

优点:

  • 码量小
  • 易于理解
  • 能够资瓷大量操作

缺点:

  • 使用局限性较大
  • 容易被卡

珂朵莉树的功能极其强大,可以说只要可以暴力做的它都能做,但是只要没有区间复制操作,那么它比暴力还多只$\log$,而且只要出题人有这个心,完全可以把你卡满,但是它作为一种骗分技巧还是非常实用的,很重要的是它学起来很简单,而且大概$10min$(也许更短?)就可以敲完。

 评论