珂朵莉树

Posted on Edited on

种一棵树最好的时间是十年前，其次是现在，或者是一棵珂朵莉树。

很早之前就听说过珂朵莉树了，不过每次点开题解看到平衡树就直接关闭了一直缺少一个契机去学习这个优雅的暴力算法。正好借着日题实在懒得写线段树了，所以终于下定决心去学习这个算法或者说一个思想更为合适。

首先先贴上板子。因为本身就是一个暴力算法，所以参考了大佬们的板子，不然自己写估计常数太大了(╯‵□′)╯︵┻━┻

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
class ChthollyTree {
		struct ChthollyNode {
			long long l;
			long long r;
			mutable long long v;
			ChthollyNode(const long long l, const long long r, const long long v): l(l), r(r), v(v) {}
			bool operator <(const ChthollyNode &o) const {
				return l < o.l;
			}
		};
	public:
		set<ChthollyNode> tree;
		ChthollyTree() {}

		set<ChthollyNode>::iterator split(long long pos) {
			auto it = tree.lower_bound(ChthollyNode(pos, 0, 0));
			if (it != tree.end() && it->l == pos)
				return it;
			it--;
			long long l = it->l;
			long long r = it->r;
			long long v = it->v;
			tree.erase(it);
			tree.insert(ChthollyNode(l, pos - 1, v));
			return tree.insert(ChthollyNode(pos, r, v)).first;
		}

		void assign(long long l, long long r, long long v) {
			auto itr = split(r + 1);
			auto itl = split(l);
			tree.erase(itl, itr);
			tree.insert(ChthollyNode(l, r, v));
		}

		void foo(long long l, long long r, long long x) {
			auto itr = split(r + 1);
			auto itl = split(l);
			for (auto it = itl; it != itr; it++) {
				//在这里添加其他的各种操作
			}
		}

		void insert(long long l, long long r, long long v) {
			tree.insert(ChthollyNode(l, r, v));
		}
};

首先，珂朵莉树实际上并不是一棵树，而是一种以近乎暴力的形式存储区间信息的一种数据结构，通过利用set存放若干个使用$ChthollyNode$表示的区间，其中每个区间的值都是相同。set的底层是使用红黑树实现的，某种程度上来说珂朵莉树确实是一颗树

只要涉及到区间赋值操作的题目，就可以考虑使用珂朵莉树来处理对于关于区间信息的查询。珂朵莉树是一种优雅的暴力，这种优雅的暴力实际上是建立在区间的合并操作上。通过区间合并，或者说区间赋值操作，可以大大减少珂朵莉节点的数量。所以，珂朵莉树要求题目必须存在区间赋值操作，而且数据需要具有高度的随机性。

这里补充几个细节。

  • 首先是$ChthollyNode$中的$v$变量使用了mutable关键字来修饰。mutable关键字定义一个强制可变量，因为珂朵莉树常常会涉及需要修改$v$的操作，这样定义后就可以直接修改节点，而不用删除原节点之后再插入修改后的节点。
  • 之后在split的时候，一定要先split(r+1)之后再split(l)，不然可能会RE。(根据洛谷大佬泥土笨笨的数据，大概1%的概率，不过如果rp–，可能会RE一片)。
  • 另外关于为什么是split(r+1)，这是因为set删除的时候是左闭右开区间。此外set的insert实际上是有返回值的：
    • 当向set容器添加元素成功时，该迭代器指向set容器新添加的元素，bool类型的值为 true；
    • 如果添加失败，即证明原set容器中已存有相同的元素，此时返回的迭代器就指向容器中相同的此元素，同时bool类型的值为false。

日题715就是板子题，这里就不贴AC代码了；下面贴一道珂朵莉树的来源(写珂朵莉树怎么可能不写这题:D)

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$ 个数是的多少(即区间第$x$ 小，数字大小相同算多次，保证 $1\leq$ $x$ $\leq$ $r-l+1$ )
  • $4$ $l$ $r$ $x$ $y$ ：输出$[l,r]$ 区间每个数字的$x$ 次方的和模$y$ 的值(即($\sum^r_{i=l}a_i^x$ ) $\mod y$ )

【输入格式】
这道题目的输入格式比较特殊，需要选手通过$seed$ 自己生成输入数据。
输入一行四个整数$n,m,seed,v_{max}$ （$1\leq $ $n,m\leq 10^{5}$ ,$0\leq seed \leq 10^{9}+7$ $,1\leq vmax \leq 10^{9} $ ）
其中$n$ 表示数列长度，$m$ 表示操作次数，后面两个用于生成输入数据。

【输出格式】
对于每个操作3和4，输出一行仅一个数。

题目描述

— Willem…

— What’s the matter?

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

— I’ll have a look…

Seniorious is made by linking special talismans in particular order.

After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.

Seniorious has $ n $ pieces of talisman. Willem puts them in a line, the $ i $ -th of which is an integer $ a_{i} $ .

In order to maintain it, Willem needs to perform $ m $ operations.

There are four types of operations:

  • $ 1\ l\ r\ x $ : For each $ i $ such that $ l<=i<=r $ , assign $ a_{i}+x $ to $ a_{i} $ .
  • $ 2\ l\ r\ x $ : For each $ i $ such that $ l<=i<=r $ , assign $ x $ to $ a_{i} $ .
  • $ 3\ l\ r\ x $ : Print the $ x $ -th smallest number in the index range $ [l,r] $ , i.e. the element at the $ x $ -th position if all the elements $ a_{i} $ such that $ l<=i<=r $ are taken and sorted into an array of non-decreasing integers. It’s guaranteed that $ 1<=x<=r-l+1 $ .
  • $ 4\ l\ r\ x\ y $ : Print the sum of the $ x $ -th power of $ a_{i} $ such that $ l<=i<=r $ , modulo $ y $ , i.e. .

输入格式

The only line contains four integers $ n,m,seed,v_{max} $ ( $ 1<=n,m<=10^{5},0<=seed<10^{9}+7,1<=vmax<=10^{9} $ ).

The initial values and operations are generated using following pseudo code:

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
def rnd():

    ret = seed
    seed = (seed * 7 + 13) mod 1000000007
    return ret

for i = 1 to n:

    a[i] = (rnd() mod vmax) + 1

for i = 1 to m:

    op = (rnd() mod 4) + 1
    l = (rnd() mod n) + 1
    r = (rnd() mod n) + 1

    if (l > r): 
         swap(l, r)

    if (op == 3):
        x = (rnd() mod (r - l + 1)) + 1
    else:
        x = (rnd() mod vmax) + 1

    if (op == 4):
        y = (rnd() mod vmax) + 1

Here $ op $ is the type of the operation mentioned in the legend.

输出格式

For each operation of types $ 3 $ or $ 4 $ , output a line containing the answer.

样例 #1

样例输入 #1

1
10 10 7 9

样例输出 #1

1
2
3
4
2
1
0
3

样例 #2

样例输入 #2

1
10 10 9 9

样例输出 #2

1
2
3
4
1
1
3
3

提示

In the first example, the initial array is $ {8,9,7,2,3,1,5,6,4,8} $ .

The operations are:

  • $ 2\ 6\ 7\ 9 $
  • $ 1\ 3\ 10\ 8 $
  • $ 4\ 4\ 6\ 2\ 4 $
  • $ 1\ 4\ 5\ 8 $
  • $ 2\ 1\ 7\ 1 $
  • $ 4\ 7\ 9\ 4\ 4 $
  • $ 1\ 2\ 7\ 9 $
  • $ 4\ 5\ 8\ 1\ 1 $
  • $ 2\ 5\ 7\ 5 $
  • $ 4\ 3\ 10\ 8\ 5 $

AC代码如下：

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
147
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

long long n, m, seed, vmax;

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


class ChthollyTree {
		struct ChthollyNode {
			long long l;
			long long r;
			mutable long long v;
			ChthollyNode(const long long l, const long long r, const long long v): l(l), r(r), v(v) {}
			bool operator <(const ChthollyNode &o) const {
				return l < o.l;
			}
		};
	public:
		set<ChthollyNode> tree;
		ChthollyTree() {}

		set<ChthollyNode>::iterator split(long long pos) {
			auto it = tree.lower_bound(ChthollyNode(pos, 0, 0));
			if (it != tree.end() && it->l == pos)
				return it;
			it--;
			long long l = it->l;
			long long r = it->r;
			long long v = it->v;
			tree.erase(it);
			tree.insert(ChthollyNode(l, pos - 1, v));
			return tree.insert(ChthollyNode(pos, r, v)).first;
		}

		void assign(long long l, long long r, long long v) {
			auto itr = split(r + 1);
			auto itl = split(l);
			tree.erase(itl, itr);
			tree.insert(ChthollyNode(l, r, v));
		}

		void add(long long l, long long r, long long x) {
			auto itr = split(r + 1);
			auto itl = split(l);
			for (auto it = itl; it != itr; it++) {
				it->v += x;
			}
		}

		long long kth(long long l, long long r, long long x) {
			auto itr = split(r + 1);
			auto itl = split(l);
			vector<pair<long long, long long>> t;
			for (auto it = itl; it != itr; it++) {
				t.push_back({it->v, it->r - it->l + 1});
			}
			sort(t.begin(), t.end());
			long long accumulate = 0;
			for (long long i = 0; i < t.size(); i++) {
				accumulate += t[i].second;
				if (accumulate >= x)
					return t[i].first;
			}
		}

		long long sum_of_pow(long long l, long long r, long long x, long long y) {
			long long ret = 0;
			auto itr = split(r + 1);
			auto itl = split(l);
			for (auto it = itl; it != itr; it++) {
				ret = (ret + pow(it->v, x, y) * (it->r - it->l + 1)) % y;
			}
			return ret;
		}

		void insert(long long l, long long r, long long v) {
			tree.insert(ChthollyNode(l, r, v));
		}

		long long pow(long long x, long long n, long long m) {
			long long ans = 1;
			long long contribution = x % m;
			while (n > 0) {
				if (n % 2 == 1)
					ans = (ans * contribution) % m;
				contribution = (contribution * contribution) % m;
				n = n >> 1;
			}
			return ans;
		}

};

int main() {
	ChthollyTree tree;
	cin >> n >> m >> seed >> vmax;
	vector<long long> a(n + 1);
	for (long long i = 1; i <= n; i++) {
		a[i] = (rnd() % vmax) + 1;
		//cout << a[i] << " ";
		tree.insert(i, i, a[i]);
	}
	//test
	/*for (long long i = 1; i <= n; i++) {
		long long t;
		cin >> t;
		tree.insert(i, i, t);
	}*/
	//test
	for (long long i = 1; i <= m; i++) {
		long long op = (rnd() % 4) + 1;
		long long l = (rnd() % n) + 1;
		long long r = (rnd() % n) + 1;
		if (l > r)
			swap(l, r);
		long long x, y;
		if (op == 3)
			x = (rnd() % (r - l + 1)) + 1;
		else
			x = (rnd() % vmax) + 1;
		if (op == 4)
			y = (rnd() % vmax) + 1;
		//test
		/*cin >> op >> l >> r >> x;
		if (op == 4)
			cin >> y;
			*/
		//test
		if (op == 1)
			tree.add(l, r, x);
		if (op == 2)
			tree.assign(l, r, x);
		if (op == 3)
			cout << tree.kth(l, r, x) << endl;
		if (op == 4)
			cout << tree.sum_of_pow(l, r, x, y) << endl;
	}
	return 0;
}

其中操作2对应的就是珂朵莉树的基本操作，其他的直接暴力统计就可以了。需要注意的是快速幂最好使用递推的版本，如果使用递归的版本会在递归的过程中爆long long。
end☆~