未来始终掌握在自己手中，从中滑落的，我们称之为过去。——《末日时在做什么？有没有空？可以来拯救吗？》

珂朵莉树

起源

珂朵莉树起源于 ，这道题要求我们实现一种数据结构，可以较快地实现区间和、区间赋值、求区间第 大值和求区间 次方和。

出自第3集18分18秒左右

就此需求来说，普通的树状数组、线段树等显然难以胜任，看上去需要一种神奇的数据结构。但是在珂学家出题人的题解中，却实现了一种简单暴力的数据结构。刚开始出题人 用自己的 将其命名为 ，后来又改而定名为珂朵莉树。

食用范围

珂朵莉树的食用范围是在有区间赋值操作且数据随机的题目。珂朵莉树看上去不是一个树状结构，而使用 里的 ，而 是用红黑树实现的，所以也不算名副其实。在随机数据下，珂朵莉树可以达到 的复杂度，链表实现复杂度为 ，理论复杂度是 。

实现和思想

珂朵莉树的思想在于随机数据下的区间赋值操作很可能让大量元素变为一个数。所以我们以三元组 的形式来保存数据（区间 中元素的值都是 ）

给出一组数据来举例

实现代码如下：

1
2
3
4
5
6
struct node {
	int l, r;
	mutable int v; // 这里 mutable 不写会 CE
	node (int l, int r, int v) : l (l), r (r), v (v) {} // 构造函数 
	bool operator < (const node &o) const { return l < o.l; } // 重载小于运算符  
};

然后把这些三元组存到 里（也可以用链表，但是 毕竟方便）：

1
set<node> tree;

要把结构体放进 里需要重载小于运算符， 会保证内部元素有序（插入、删除和查询的时间复杂度都是 ）。而 使得当整个结构体为 时，标为 的成员仍可变（因为可能有区间加等操作）。

珂朵莉树的食用

断开区间

但是有的时候在进行区间操作时，会把原本连续的区间断开。所以我们需要一个能实现”断开“操作的函数，把 断成 和 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
set<node>::iterator split (int pos)
// 若支持 c++ 14 ，可以把 set<node>::iterator 换成 auto 
{
	set<node>::iterator it = tree.lower_bound (node (pos, 0, 0)); // 寻找左端点第一个大于等于 pos 的节点 
	// 若支持 c++ 11 ，可以把 set<node>::iterator 改成 auto
	if (it != tree.end () && it -> l == pos) // 如果已经存在以 pos 为端点的点，直接返回 
		return it;
	it --; // 否则向前数一个节点  
	int l = it -> l, r = it -> r, v = it -> v;
	tree.erase (it); // 删除该节点 
	tree.insert (node (l, pos - 1, v)); // 插入 <l, pos - 1, v> 和 <pos, r, v> 
	return tree.insert (node (pos, r, v)).first; // 返回以 pos 为开头的迭代器
	// insert 默认返回值是一个 pair ，然后我们需要第一个成员 
}

看懂了吗？反正我是没看懂，所以例行模拟：

就此模拟！！！

假设我们现在要 ，首先 _ 找到区间左端点大于等于 的节点，是 ，但是它的左端点不是 ，所以回退，得 。然后把节点 删除，然后插入 和 即可。

模拟完成

区间赋值

珂朵莉树的精髓在区间赋值，而写法也很简单：

1
2
3
4
5
6
void assign (int l, int r, int v) // 区间赋值  
{
	auto end = split (r + 1), begin = split (l); // 顺序不能颠倒，否则可能 RE
	tree.erase (begin, end); // 删除中间的节点 
	tree.insert (node (l, r, v)); // 插入新的节点 
}

要做的就是删掉范围内的节点，然后换上新的（范围较大）的节点。只是需要注意求 和 的顺序不能颠倒，因为 可能把 原来所在的节点断开。

区间和

…… 似乎很麻烦，那直接暴力吧！

1
2
3
4
5
6
void add (int l, int r, int v) // 区间和 
{
	auto end = split (r + 1); // 区间右端点 
	for (auto it = split (l); it != end; it ++) // 从区间左端点开始遍历，逐个加  
		it -> v += v;
}

求区间 k 大值

我们可以借助一个 ，把区间丢进去直接排个序，然后再挨个丢出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int rank (int l, int r, int k) // 求区间 k 大值 
{
	auto end = split (r + 1); // 得到右端点  
	vector<pair<int, int > > v; // 这个 pair 里面存节点的值和区间长度 
	for (auto it = split (l); it != end; it ++) // 区间遍历  
		v.push_back (make_pair (it -> v, it -> r - it -> l + 1)); // 给 pair 赋值，节点值和区间长度
	sort (v.begin (), v.end ()); // 按节点大小排序 
	for (int i = 0; i < v.size (); i ++) // 挨个区间丢出来，直到丢出 k 个元素为止 
	{
		k -= v[i].second; // 第二个成员存的是长度，不要搞错  
		if (k <= 0)
			return v[i].first; // 第一个成员存的是值，不要搞错  
	}
}

求区间 n 次方和

直接用快速幂求，熟悉的遍历，陌生的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline int qpow (int x, int p, int mod) // 快速幂 
{
	int res = 1;
	while (p)
	{
		if (p & 1)
			res = res * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return res;
}
int sum_pow (int l, int r, int p, int mod) // 求区间 n 次方和 
{
	int tot = 0;
	auto end = split (r + 1);
	for (auto it = split (l); it != end; it ++)
		tot = (tot + qpow (it -> v, p, mod) * (it -> r - it -> l + 1)) % mod;
	return tot;
}

例题

Willem, Chtholly and Seniorious

  • Willem…

  • What’s the matter?

  • It seems that there’s something wrong with Seniorious…

  • I’ll have a look…

瑟尼欧里斯是由一块块幸运符合成的，现在威廉要对这些幸运符做如下操作：

1、求区间能力值

2、对一段区间赋值

3、求区间内最大能力值

4、求区间 次方和

下面给出 的代码：

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
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define It set<node>::iterator

typedef long long ll;
 
using namespace std;

const ll mod7 = 1e9 + 7;
const ll N = 1e5 + 1;
ll n, m, seed, vmax;
ll a[N];

struct node {
	ll l, r;
	mutable ll v;
	node (ll l, ll r, ll v) : l (l), r (r), v (v) {};
	bool operator < (const node &o) const { return l < o.l; }
};

set<node> tree;

inline ll qpow (ll x, ll p, ll mod)
{
	ll res = 1;
	ll ans = x % mod;
	while (p)
	{
		if (p & 1)
			res = res * ans % mod;
		ans = ans * ans % mod;
		p >>= 1;
	}
	return res;
}

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

void add (ll l, ll r, ll v)
{
	It end = split (r + 1);
	for (It it = split (l); it != end; it ++)
		it -> v += v;
}

void assign (ll l, ll r, ll v)
{
	It end = split (r + 1), begin = split (l);
	tree.erase (begin, end);
	tree.insert (node (l, r, v));
}

ll rankk (ll l, ll r, ll k)
{
	It end = split (r + 1);
	vector <pair<ll, ll> > v;
	for (It it = split (l); it != end; it ++)
		v.push_back (make_pair (it -> v, it -> r - it -> l + 1));
	sort (v.begin (), v.end ());
	for (int i = 0; i < v.size (); i ++)
	{
		k -= v[i].second;
		if (k <= 0)
			return v[i].first;
	}
}

ll sum_pow (ll l, ll r, ll p, ll mod)
{
	ll tot = 0;
	It end = split (r + 1);
	for (It it = split (l); it != end; it ++)
		tot = (tot + qpow (it -> v, p, mod) * (it -> r - it -> l + 1)) % mod;
	return tot;
}

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

signed main ()
{
	scanf ("%lld %lld %lld %lld", &n, &m, &seed, &vmax);
	for (int i = 1; i <= n; i ++)
	{
		a[i] = (rnd () % vmax) + 1;
		tree.insert (node (i, i, a[i]));
	}
	tree.insert (node (n + 1, n + 1, 0));
	for (int i = 1; i <= m; i ++)
	{
		ll op = rnd () % 4 + 1, l = rnd () % n + 1, r = rnd () % n + 1, x, y;
		if (l > r)
			swap (l, r);
		if (op == 3)
			x = int (rnd () % (r - l + 1)) + 1;
		else
			x = int (rnd () % vmax) + 1;
		if (op == 4)
			y = int (rnd () % vmax) + 1;
		if (op == 1)
			add (l, r, x);
		else if (op == 2)
			assign (l, r, x);
		else if (op == 3)
			printf ("%lld\n", rankk (l, r, x));
		else 
			printf ("%lld\n", sum_pow (l, r, x, y));
	}
	return 0;
}