珂朵莉树学习笔记

发表于 | 更新于 | 评论数：

珂朵莉树是一种暴力数据结构，代码较短，原理简单。适用于骗分和暴力对拍。

适用范围

  • 含有区间赋值操作。
  • 操作随机或者区间赋值操作较多。
  • 维护区间高次幂。

主要原理

把连续一段相同的值合并成一块，用set维护这些块。

随机数据下期望复杂度$O(m\log n)$（$m$为操作数，$n$为序列内数字个数）。

基本操作

Node

1
2
3
4
5
6
7
8
9
struct Node {
    int l, r;
	mutable int v;
	Node() {}
	Node(int x, int y = -1, int z = 0) : l(x), r(y), v(z) {}
	bool operator < (const Node &rhs) const { 
		return l < rhs.l;
	}
};

注意：用iterator修改值时，该值必须为mutable形式。默认是只读，不这样写不能编译通过。

split

把一个块分裂为两块。

1
2
3
4
5
6
7
8
9
10
11
12
set<Node> s;
typedef set<Node>::iterator Iter;
Iter split(int pos) {
	Iter it = s.lower_bound(Node(pos));
	if (it != s.end() && it->l == pos) // ***
		return it;
	--it;
	int l = it->l, r = it->r, v = it->v; // *** 
	s.erase(it);
	s.insert(Node(l, pos - 1, v));
	return s.insert(Node(pos, r, v)).first;
}

默认的insert是std::pair<iterator,bool> insert(const value_type &value)，这里用它的返回值first。

注意：

  • if内的先后顺序，颠倒后会访问空指针出错。
  • 后面的erase和insert会使当前的it指针失效，指向其他地方，所以要先记下来这些值。
  • 函数内含有erase，可能会使其他iterator失效，调用的时候应注意这种情况。

assign

把连续相同数字的区间合并成一块。是珂朵莉在随机数据下复杂度的保证。

在随机数据下，每次合并的期望长度为$\frac{n}{3}$。

1
2
3
4
5
void assign(int l, int r, int v) {
	Iter itr = split(r + 1), itl = split(l); // ***
	s.erase(itl, itr);
	s.insert(Node(l, r, v));
}

void erase(iterator first, iterator last)可删除[first,last)区间。

注意：取区间的时候应当先取后面再取前面，否则取完前面后，后面的指针会发生变化。

其他操作

全是暴力，具体见代码。

题目

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i_, s_, t_) for (int i_ = (s_); i_ <= (t_); ++i_)
typedef long long ll;

const int N = 1e5 + 5, P = 1e9 + 7;
int a[N];
ll seed;

ll qpow(ll o, int x, int mod) {
	ll res = 1;
	o %= mod; // ***
	for (; x; o = o * o % mod, x >>= 1)
		if (x & 1)
			res = res * o % mod;
	return res;
}

struct Node {
	int l, r;
	mutable ll v;
	Node() {}
	Node(int x, int y = -1, ll z = 0) : l(x), r(y), v(z) {}
	bool operator < (const Node &rhs) const {
		return l < rhs.l;
	}
};

typedef set<Node>::iterator Iter;
set<Node> s;

Iter split(int p) {
	Iter it = s.lower_bound(Node(p));
	if (it != s.end() && it->l == p)
		return it;
	it--;
	// ***
	int l = it->l, r = it->r;
	ll val = it->v;
	s.erase(it);
	s.insert(Node(l, p - 1, val));
	return s.insert(Node(p, r, val)).first;
}

void assign(int l, int r, ll v = 0) {
	Iter itr = split(r + 1), itl = split(l);
	s.erase(itl, itr);
	s.insert(Node(l, r, v));
}

void add(int l, int r, int val) {
	Iter itr = split(r + 1), itl = split(l);
	for (; itl != itr; ++itl)
		itl->v += val;
}

ll kth(int l, int r, int k) {
	vector<pair<ll, int> > t;
	Iter itr = split(r + 1), itl = split(l);
	t.clear();
	for (; itl != itr; ++itl)
		t.push_back(make_pair(itl->v, itl->r - itl->l + 1)); // ***
	sort(t.begin(), t.end());
	/* for (Iter it = t.begin(); it != t.end(); ++it) { */
	for (vector<pair<ll, int> >::iterator it = t.begin(); it != t.end(); ++it) {
		k -= it->second;
		if (k <= 0)
			return it->first;
	}
	return -1;
}

ll sum(int l, int r, int x, int mod) {
	Iter itr = split(r + 1), itl = split(l);
	ll ans = 0;
	for (; itl != itr; ++itl)
		ans = (ans + 1ll * (itl->r - itl->l + 1) * qpow(itl->v, x, mod) % mod) % mod;
	return ans;
}

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

int main() {
	//freopen("CF896C.out", "w", stdout);
	int n, m, vmax, op, l, r, x, y = 0;
	scanf("%d%d%lld%d", &n, &m, &seed, &vmax);
	rep (i, 1, n) {
		a[i] = rnd() % vmax + 1;
		s.insert(Node(i, i, a[i]));
	}
	s.insert(Node(n + 1, n + 1, 0));
	rep (i, 1, m) {
		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;
		if (op == 1)
			add(l, r, x);
		else if (op == 2)
			assign(l, r, x);
		else if (op == 3)
			printf("%lld\n", kth(l, r, x));
		else
			printf("%lld\n", sum(l, r, x, y));
	}
}

再放一些其他能用珂朵莉树的题。

  1. CF343D Water Tree

  2. P2572 [SCOI2010]序列操作

  3. P4344 [SHOI2015]脑洞治疗仪

  4. CF915E Physical Education Lessons

  5. P2787 语文1（chin1）- 理理思维

  6. P4979 矿洞：坍塌

目前来看，大多数出题人都没有刻意去卡珂朵莉树，但是大部分情况下，由于数据不是随机，复杂度都是错的。

要谨慎使用。

2019.5.5更新：

P5350序列。

标算是珂朵莉树。这道题有copy和swap操作，会在其中删除一部分，再插入一部分。在右端点$r$已经被删除的情况下，如果下一次还要$split(r)$，就会产生类似于$[r, r - 1]$的错误区间，会对答案产生影响。

解决方法：先取小再取大；或者在出现这种情况的时候特判一下。因为已经$split$过右端点，只需要判断是否小于等于它就好，不需要比较指针了。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i_, s_, t_) for (int i_ = (s_); i_ <= (t_); ++i_)

typedef long long ll;
const int N = 3e5 + 5, P = 1e9 + 7;

struct Node {
	int l, r;
	mutable ll v;
	Node() {}
	Node(int x, int y = -1, ll z = 0) : l(x), r(y), v(z) {}
	bool operator < (const Node &rhs) const {
		return l < rhs.l;
	}
} q[N], *top;

typedef set<Node>::iterator Iter;
set<Node> s;

Iter split(int p) {
	Iter it = s.lower_bound(Node(p));
	if (it != s.end() && it->l == p)
		return it;
	--it;
	int l = it->l, r = it->r;
	ll val = it->v;
	s.erase(it);
	s.insert(Node(l, p - 1, val));
	return s.insert(Node(p, r, val)).first;
}

void assign(int l, int r, ll v) {
	Iter itr = split(r + 1), itl = split(l);
	s.erase(itl, itr);
	s.insert(Node(l, r, v));
}

void add(int l, int r, int val) {
	Iter itr = split(r + 1), itl = split(l);
	for (; itl != itr; ++itl)
		itl->v = (itl->v + val) % P;
}

ll sum(int l, int r) {
	Iter itr = split(r + 1), itl = split(l);
	ll ans = 0;
	for (; itl != itr; ++itl)
		ans = (ans + 1ll * (itl->r - itl->l + 1) * itl->v % P) % P;
	return ans;
}

void copy(int l1, int r1, int l2, int r2) {
	Iter itr2 = split(r2 + 1), itl2 = split(l2);
    s.erase(itl2, itr2);
    Iter itr1 = split(r1 + 1), itl1 = split(l1);
    int t = l2 - l1;
    for (; itl1 != itr1; ++itl1)
        s.insert(Node(itl1->l + t, itl1->r + t, itl1->v));
}

void swp(int l1, int r1, int l2, int r2) {
    int t = l2 - l1;
    top = q;
    Iter itr2 = split(r2 + 1), itl2 = split(l2), it = itl2;
    for (; it != itr2; ++it)
        *(++top) = Node(it->l - t, it->r - t, it->v);
    s.erase(itl2, itr2);
    Iter itr1 = split(r1 + 1), itl1 = split(l1);
    it = itl1;
    for (; it != itr1; ++it)
        s.insert(Node(it->l + t, it->r + t, it->v));
    s.erase(itl1, itr1);
    while (top > q)
        s.insert(*(top--));
}

void rev(int l, int r) {
    int t = l + r;
    Iter itr = split(r + 1), itl = split(l), it = itl;
    top = q;
    for (; it != itr; ++it)
        *(++top) = *it;
    s.erase(itl, itr);
    while (top > q)
        s.insert(Node(t - top->r, t - top->l, top->v)), --top;
}

char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

template<typename T>
void read(T &x) {
    char ch;
    while (!isdigit(ch = getc()));
    for (x = ch - '0'; isdigit(ch = getc()); x = x * 10 + ch - '0');
}

int main() {
    freopen("test.in", "r", stdin);
	int n, m, op, l, r, x, y;
    read(n), read(m);
	s.insert(Node(n + 1, n + 1, 0));
    rep (i, 1, n)
        read(x), s.insert(Node(i, i, x));
	rep (i, 1, m) {
        read(op), read(l), read(r);
		if (op == 1)
			printf("%lld\n", sum(l, r));
		else if (op == 2)
			read(x), assign(l, r, x);
		else if (op == 3)
			read(x), add(l, r, x);
		else if (op == 4)
            read(x), read(y), copy(l, r, x, y);
        else if (op == 5)
            read(x), read(y), swp(l, r, x, y);
        else rev(l, r);
	}
    Iter itr = split(n + 1), itl = split(1);
    for(; itl != itr; ++itl)
        rep (i, itl->l, itl->r)
            printf("%lld ", itl->v % P);
    puts("");
}