专栏文章

珂朵莉树学习笔记

封封禁用户
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipuxeec
此快照首次捕获于
2025/12/03 18:21
3 个月前
此快照最后确认于
2025/12/03 18:21
3 个月前
查看原文

前言

终于学到了比分块更加美丽暴力的数据结构。一是因为它比分块更加暴力，二是珂朵莉本来就很美丽。
我 TM 从 oiwiki 上学的代码还能不一样吗？？？

原理

珂朵莉树（odt），又名颜色段均摊。它维护的每一个区间里都是相同的数据。例如序列 1 2 2 3 4 1 在 odt 中就使用 5 个区间维护。
由于 odt 需要频繁的插入和删除区间，所以通常选择 set 维护。set 里是一些结构体维护的区间，又因为区间的数据需要修改，所以区间的数值 vv 前面要加上关键字 mutable。
下面是定义 odt 的示例。
CPP
struct Node {
	int l, r;
	mutable int v;
	
	Node(int x, int y, int z) {
		l = x, r = y, v = z;
	}
	
	bool operator < (const Node & x) const {
		return l < x.l;
	} 
};

set<Node> odt;
初始化的时候因题目而异，有时插入一个 11 到 nn 的区间（值是题目给定的）。有时把每个数当作一个长度为 11 的区间插入进去。
然后是 odt 的核心操作 split 和 assign。

split 操作

split 做的事就是找到 xx 所在的区间 [l,r][l,r]，并且把这个区间分裂成 [l,x−1][l,x - 1] 和 [x,r][x,r]，然后返回分裂完的右区间的迭代器。
首先查找 xx 所在的区间，直接用 lower_bound 暴力找就好了（对就是这么暴力）。由于用区间的 ll 作为第一关键字，找到的区间要么左端点是 xx，此时就不用分裂了，直接 return；要么是包含 xx 的区间的下一个区间，此时上一个区间就是要找的区间，迭代器自减。
找到区间之后直接把它 erase 掉，再插入 [l,x−1][l,x - 1] 和 [x,r][x,r]。
于是 split 操作结束。
CPP
auto split(int x) {
	auto it = odt.lower_bound({x, 0, 0});//按第一关键字排序，后面两个随便填
	if (it != odt.end() && it -> l == x) return it;//如果当前区间的左端点就是这个区间
	it--;//否则要找的就是上一个区间
	int l = it -> l, r = it -> r, v = it -> v;//要先把当前区间的信息记录下来，erase 掉后就用不了了。	
	odt.erase(it);
	odt.insert({l, x - 1, v});
	return odt.insert({x, r, v}).first;
}

assign 操作

此操作完成的事很简单，就是把区间 [l,r][l,r] 推平，并赋值成 vv。
这个操作直接利用 split 完成就很简单，具体见代码注释。
CPP
void assign(int l, int r, int v) {
	auto itr = split(r + 1), itl = split(l);
//注意先split(r + 1)，再split(l)，因为如果先把左边的区间 erase 掉再找右边的区间会出问题
//再注意理解为什么是 r + 1 而不是 r
//需要操作的区间是到 r 的，所以 split 时为了把 r 点包含进去应该 split 到 r + 1。
	odt.erase(itl, itr);
	odt.insert({l, r, v});
}

其他操作

其他操作就是题目中给定的各种操作。先把要操作的区间 split 出来，再进行各种修改和查询操作就好了。
CPP
void myfunction(int l, int r, int x) {
	auto itr = split(r + 1), itl = split(l);
	for (;itl != itr;itl++) {
        //各种操作各种操作各种操作
    }
}

odt 的应用

CF896C Willem, Chtholly and Seniorious

珂朵莉起源题对吧。
对于操作 11 和 22 是很好用珂朵莉树维护的。考虑操作 33 和 44 怎么完成（虽然似乎不用怎么考虑）。
对于操作 33，我们直接将每个值和这个值的个数加到 vector 里面，然后直接 sort 一遍，接着遍历一遍找到 kk 大值。
对于操作 44 （kk 方和）就是很经典的求和操作了。对于每一个值分别求它的幂，然后加起来就好了。
于是这道题迎刃而解。
CPP
#include<bits/stdc++.h>

#define int long long

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;
typedef pair<int, int> PII;

int n, m, seed, Vmax;

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

set<Node> odt;

auto split(int x) {
	auto it = odt.lower_bound({x, 0, 0});
	if (it != odt.end() && it -> l == x) return it;
	it--;
	int l = it -> l, r = it -> r, v = it -> v;
	if (r < x) return odt.end();	
	odt.erase(it);
	odt.insert({l, x - 1, v});
	return odt.insert({x, r, v}).first;
}

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

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

int len(auto it) {
	return it -> r - it -> l + 1;
}

int qpow(int a, int p, int mod) {
	int ans = 1;a %= mod;
	while (p) {
		if (p & 1) ans *= a, ans %= mod;
		a *= a, a %= mod;
		p >>= 1;
	}
	return ans;
}

int query(int l, int r, int p, int mod) {
//	cout << l << ' ' << r << ' ' << p << ' ' << mod;
	auto itr = split(r + 1), itl = split(l);
	int cnt = 0;
	for (;itl != itr;itl++) cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
	return cnt;
}

int kth(int l, int r, int k) {
    vector<PII> a;
    auto itr = split(r + 1), itl = split(l);
    for (auto iter = itl;iter != itr;iter++) a.push_back(PII(iter -> v, (iter -> r) - (iter -> l) + 1));
    sort(a.begin(),a.end());
    for (auto iter = a.begin();iter != a.end();iter++) {
	    k -= iter -> second;
	    if (k <= 0) return iter -> first;
	}
	return -1;
}

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

signed main() {
	n = read(), m = read(), seed = read(), Vmax = read();
	for (int i = 1;i <= n;i++) odt.insert(Node(i, i, (rnd() % Vmax) + 1));
	
	while (m--) {
		int op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, y;
		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 : {add(l, r, x);break;}
			case 2 : {assign(l, r, x);break;}
			case 3 : {write(kth(l, r, x)), putchar(10);break;}
			case 4 : {write(query(l, r, x, y)), putchar(10);break;}
			default : break;
		}
		
//		for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
	}
	
	return 0;
}
注意这个快速幂里面底数先要模模数，否则会 WA #3。

P3071 [USACO13JAN] Seating G

什么？最左的连续空位？还有区间推平？ 于是自然想到珂朵莉树解决。
初始化时先插入一个 11 到 nn，值为 00 的区间，表示初始全为空座位。
找最左的连续 aa 个空位，直接暴力循环一遍就好了，别忘了把相邻的空区间的长度累加起来，否则就会 WA 20pts。
客人离开就是区间推平，直接 assign 即可。
CPP
#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

constexpr int maxn = 5e5 + 5;

int n, m;

struct Node {
	int l, r;
	mutable int v;
	
	Node(int L, int R, int V) {l = L, r = R, v = V;}
	
	bool operator < (const Node & x) const {
		return l < x.l;
	}
};

set<Node> odt;

auto split(int x) {
	auto it = odt.lower_bound(Node(x, 0, 0));
	if (it != odt.end() && it -> l == x) return it;
	it--;
	int l = it -> l, r = it -> r, val = it -> v;
	if (r < x) return odt.end();
	odt.erase(it);
	odt.insert(Node(l, x - 1, val));
	return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
	auto itr = split(r + 1), itl = split(l);
	odt.erase(itl, itr);
	odt.insert(Node(l, r, val));
}

int len(auto x) {
	return x.r - x.l + 1;
}

int update(int x) {
//	auto rit = split(y + 1), lit = split(x);
//	for (auto i : odt) {
//		if (i.v == 1) continue;
//		if (len(i) >= x) {
//			Assign(i.l, i.l + x, 1);
//			return 0;
//		}
//	}
	
	int tot = 0, cnt = 0, frm = -1;
	for (auto i : odt) {
		if (i.v == 0) {
			cnt += len(i);
			if (frm == -1) frm = i.l;
		}
		else cnt = 0, frm = -1;
		tot = max(tot, cnt);
		if (tot >= x) {
			Assign(frm, frm + x - 1, 1);
			return 0;
		}
	}
	return 1;
}

int main() {
	n = read(), m = read();
	
	odt.insert(Node(1, n, 0));
	
	int ans = 0;
	while (m--) {
		char ch;cin >> ch;
		int x = read(), y;
		if (ch == 'A') ans += update(x);
		else y = read(), Assign(x, y, 0); 
//		for (auto i : odt) {
//			cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//		}
	}
	
	write(ans), putchar(10);
	return 0;
}

P4344 [SHOI2015] 脑洞治疗仪

众所周知的，这道题被卡了对吧。所以这是 100100 pts 做法（unaccepted）。
操作 00 就是推平，操作 11 用 vector 记下来再填进去（注意 split 和 erase 之间的顺序），操作 22 就类似上一题的做法统计最长的空区间。
CPP
#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

constexpr int maxn = 2e5 + 5;

int n, m;

struct Node {
	int l, r;
	mutable int v;
	
	Node(int L, int R, int V) {
		l = L, r = R, v = V;
	}
	
	bool operator < (const Node & x) const {
		return l < x.l;
	}
};

set<Node> odt;

auto split(int x) {
	auto it = odt.lower_bound(Node(x, 0, 0));
	if (it != odt.end() && it -> l == x) return it;
	it--;
	int l = it -> l, r = it -> r, val = it -> v;
	if (r < x) return odt.end();
	odt.erase(it);
	odt.insert(Node(l, x - 1, val));
	return odt.insert(Node(x, r, val)).first; 
}

void Assign(int l, int r, int val) {
	auto itr = split(r + 1), itl = split(l);
	odt.erase(itl, itr);
	odt.insert(Node(l, r, val));
}

int len(auto x) {
	return x -> r - x -> l + 1;
}

void update(int l1, int r1, int l2, int r2) {
	auto rit = split(r1 + 1), lit = split(l1), L = lit;
//	int cnt = 0;
//	for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit), lit -> v = 0;
	
	
	int cnt = 0;
	for (;lit != rit;lit++) if (lit -> v == 1) cnt += len(lit);
	Assign(l1, r1, 0);
//	for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
//	putchar(10);
	rit = split(r2 + 1), lit = split(l2);
	for (;lit != rit;lit++) {
		if (lit -> v == 1) continue;
		if (cnt >= len(lit)) cnt -= len(lit), lit -> v = 1;
		else {
			if (cnt != 0) Assign(lit -> l, lit -> l + cnt - 1, 1);
			break;
		}
	}
}

int perform(int l, int r) {
	auto rit = split(r + 1), lit = split(l);
	int ans = 0, cnt = 0;
	for (;lit != rit;lit++) {
//		cout << lit -> l << ' ' << lit -> r << ' ' << lit -> v << '\n';
		if (lit -> v == 0) cnt += len(lit);
		else ans = max(ans, cnt), cnt = 0;
	}
	ans = max(ans, cnt);
	return ans;
}

int main() {
	n = read(), m = read();
	
	odt.insert(Node(1, n + 1, 1));
	
	while (m--) {
		int op = read(), x = read(), y = read();
		if (op == 0) Assign(x, y, 0);
		if (op == 1) {
			int u = read(), v = read();
			update(x, y, u, v);
		}
		if (op == 2) write(perform(x, y)), putchar(10);
	}
	
	return 0;
}

P7134 小 H 的序列

https://www.luogu.com.cn/problem/P7134。
这个查询操作看起来十分像珂朵莉树的起源题对吧，所以自然想到珂朵莉树解决。
操作一似乎不能直接推平，考虑把每个区间转存到数组里面，再把操作区间删掉，然后把相邻且值相同的区间合并之后再加到珂朵莉树中。
询问操作就是很典的珂树了，把每个树里的的区间一起计算 vpv ^ {p}，再乘上区间长度，累加到答案。
CPP
#include<bits/stdc++.h>

#define int unsigned long long

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;

int n, m;

struct Node {
	int l, r;
	mutable int v;
	
//	Node(int x, int y, int z) {
//		l = x, r = y, v = z;
//	}
	
	bool operator < (const Node & x) const {
		return l < x.l;
	} 
};

set<Node> odt;

auto split(int x) {
	auto it = odt.lower_bound({x, 0, 0});
	if (it != odt.end() && it -> l == x) return it;
	it--;
	int l = it -> l, r = it -> r, v = it -> v;
	if (r < x) return odt.end();	
	odt.erase(it);
	odt.insert({l, x - 1, v});
	return odt.insert({x, r, v}).first;
}

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


int MOD[maxn], Val[maxn];
int qpow(int a, int p, int mod) {
	int ans = 1LL, A = a;
	
	if (MOD[A] == mod) return Val[A];

	while (p) {
		if (p & 1) ans *= a, ans %= mod;
		a *= a, a %= mod;
		p >>= 1;
	}
	
	Val[A] = ans, MOD[A] = mod;
	
//	cout << ans << '\n'; 
	return ans % mod;
}

void update(int l, int r, int x, int y, int d) {
//	cout << l << ' ' << r << ' ' << x << ' ' << y << ' ' << d << '\n';
	auto itr = split(r + 1), itl = split(l);Node its[maxn];
	int tot = 1, nowx = 0;
	for (auto i = itl;i != itr;i++) {
		int v = i -> v;
		its[++tot] = *i;
		if (v <= y && v >= x) its[tot].v = d;
	}
	
	odt.erase(itl, itr);
	
	for (int i = 1;i <= tot;i++) {
		if (i == 1 || its[i].v != its[i - 1].v) {
			if (nowx) odt.insert({nowx, its[i - 1].r, its[i - 1].v});
			nowx = its[i].l;
		}
	}
	odt.insert({nowx, r, its[tot].v});
}

int len(auto it) {
	return it -> r - it -> l + 1;
}

int query(int l, int r, int p, int mod) {
//	cout << l << ' ' << r << ' ' << p << ' ' << mod << '\n';
	auto itr = split(r + 1), itl = split(l);
//	cout << itl -> l << ' ' << itr -> r;
	int cnt = 0;
	for (;itl != itr;itl++) {
//		cout << itl -> l << ' ' << itl -> r << ' ' << itl -> v << ' ' << len(itl) << '\n';
//		(((cnt += qpow(itl -> v, p, mod)) %= mod) *= len(itl)) %= mod;
		cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
//		cout << qpow(itl -> v, p, mod) << "nailong " << cnt << '\n';
	}
//	cout << cnt << '\n';
	return cnt;
}

signed main() {
	n = read(), m = read();
	
	for (int i = 1;i <= n;i++) odt.insert({i, i, read()});
	
	int Ans = 0;
	
	while (m--) {
		int op = read(), l = read(), r = read(), u = read(), v = read(), t;
		if (op == 0) t = read(), update(l, r, u, v, t);
		else Ans ^= query(l, r, u, v);
		
//		for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
	}
	
	write(Ans), putchar(10);
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...