珂朵莉树浅析
0. 关于珂朵莉
1. 珂朵莉树实现
珂朵莉树（也称 Old Driver Tree），是一种暴力数据结构，其代表的操作有：
- 区间推平（将区间 \([l,r]\) 的数修改为 \(x\)）；
- 区间次幂和（给定 \(x,y\)，计算 \(\sum_{l\le i\le r} a_i^x \bmod y\)）。
当然珂朵莉树也可以做到区间加，区间第 \(x\) 小等操作。
珂朵莉树适用于数据随机的情况，平均时间复杂度 \(O(m\log n)\)。
接下来以 CF896C Willem, Chtholly and Seniorious 为例，讲解珂朵莉树的实现方式。
1.1 初始化
珂朵莉树是以一个结构体 Node 为基础的，我们对于每一个区间，定义 \(l,r,v\)，分别表示区间左端点，区间右端点和区间中的值。
struct Node {
int l, r; // 左右端点
mutable int v; // 区间中的值, mutable表示v虽然是常量,但是可修改
Node (int l, int r = 0, int v = 0) : l(l), r(r), v(v) {} // 成员函数,创造一个为(l,r,v)的区间
bool operator < (const Node &a) const { // 重载<运算符, 便于排序
return l < a.l;
}
};
接下来我们需要用一个 set \(s\) 来存储这些区间，由于我们重载了运算符，所以 \(s\) 中的区间会按左端点从小到大排序。
1.2 Split 操作
珂朵莉树的关键操作就是 split，它可以将区间 \([l,r]\) 划分为两个区间 \([l,pos-1]\) 和 \([pos,r]\)。
set<Node>::iterator split(int pos) { // 分割操作
set<Node>::iterator it = s.lower_bound(Node(pos)); // 找到第一个左端点不小于pos的区间
if (it != s.end() && it->l == pos) return it; // pos本身就是区间左端点,直接返回
it --;
if (it->r < pos) return s.end(); //pos过大,超出了最后一个区间的范围
int l = it->l, r = it->r, v = it->v;
s.erase(it), s.insert(Node(l, pos-1, v)); // 将区间[l,r]分为两段[l,pos-1]和[pos,r]
return s.insert(Node(pos, r, v)).first; // 返回后一个区间的迭代器
}
1.3 Assign 操作
珂朵莉树不仅需要划分操作，还需要合并操作 assign，它可以将 \([l,r]\) 合并为一个区间，并赋值为 \(x\)。
void assign(int l, int r, int x) { // 合并区间[l,r],并赋值为x
set<Node>::iterator itr = split(r+1), itl = split(l); // itr为r所在的区间的后一个区间的迭代器, itl为l所在的区间的迭代器
s.erase(itl, itr); // 删去itl~itr中的所有区间
s.insert(Node(l, r, x)); // 插入一个区间, 左端点为l, 右端点为r, 区间值为x
}
1.4 其他操作
其他操作基本都和 assign 操作差不多。
区间和：
void add(int l, int r, int x) { // 区间加
set<Node>::iterator itr = split(r+1), itl = split(l);
for (set<Node>::iterator it = itl; it != itr; ++it)
it->v += x;
}
区间第 \(x\) 小：
struct Rank { // 定义一个结构体,存储每一个数的数值和数量
int num, cnt;
Rank (int num, int cnt) : num(num), cnt(cnt) {}
bool operator < (const Rank &a) const {
return num < a.num;
}
};
int rnk(int l, int r, int x) { // 查询区间第x小
set<Node>::iterator itr = split(r+1), itl = split(l);
vector<Rank> v;
for (set<Node>::iterator it = itl; it != itr; ++it)
v.push_back(Rank(it->v, it->r - it->l + 1)); // 一个区间[l,r]中, 有r-l+1个v, 将其插入vector
sort(v.begin(), v.end()); // 将v中的区间按数值排序
int i = 0;
for ( ; i < v.size(); ++i) {
if (v[i].cnt < x) {
x -= v[i].cnt;
} else {
break;
}
}
return v[i].num;
}
区间次幂和：
int pow(int a, int b, int p) {
int ans = 1;
a %= p;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int cal(int l, int r, int x, int y) { // 计算区间x次幂
set<Node>::iterator itr = split(r+1), itl = split(l);
int ans = 0;
for (set<Node>::iterator it = itl; it != itr; ++it)
ans = (ans + pow(it->v, x, y)*(it->r - it->l + 1) % y) % y;
return ans;
}
1.5 完整代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int N = 1e5+10;
int n, m, seed, vmax;
int a[N];
int rnd() {
int ret = seed;
seed = (seed * 7ll + 13) % mod;
return ret;
}
struct Node {
int l, r;
mutable int v;
Node (int l, int r = 0, int v = 0) : l(l), r(r), v(v) {}
bool operator < (const Node &a) const {
return l < a.l;
}
};
set<Node> s;
set<Node>::iterator split(int pos) { // 分割操作
set<Node>::iterator it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos) return it; // pos本身就是区间左端点
it --;
if (it->r < pos) return s.end(); //pos过大
int l = it->l, r = it->r, v = it->v;
s.erase(it), s.insert(Node(l, pos-1, v)); // 将区间[l,r]分为两段[l,pos-1]和[pos,r]
return s.insert(Node(pos, r, v)).first; // 返回后一个区间的迭代器
}
void assign(int l, int r, int x) { // 合并两个区间,并赋值为x
set<Node>::iterator itr = split(r+1), itl = split(l);
s.erase(itl, itr);
s.insert(Node(l, r, x));
}
void add(int l, int r, int x) { // 区间加
set<Node>::iterator itr = split(r+1), itl = split(l);
for (set<Node>::iterator it = itl; it != itr; ++it)
it->v += x;
}
struct Rank {
int num, cnt;
Rank (int num, int cnt) : num(num), cnt(cnt) {}
bool operator < (const Rank &a) const {
return num < a.num;
}
};
int rnk(int l, int r, int x) { // 查询区间第x小
set<Node>::iterator itr = split(r+1), itl = split(l);
vector<Rank> v;
for (set<Node>::iterator it = itl; it != itr; ++it)
v.push_back(Rank(it->v, it->r - it->l + 1));
sort(v.begin(), v.end());
int i = 0;
for ( ; i < v.size(); ++i) {
if (v[i].cnt < x) {
x -= v[i].cnt;
} else {
break;
}
}
return v[i].num;
}
int pow(int a, int b, int p) {
int ans = 1;
a %= p;
while (b) {
if (b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
int cal(int l, int r, int x, int y) { // 计算区间x次幂
set<Node>::iterator itr = split(r+1), itl = split(l);
int ans = 0;
for (set<Node>::iterator it = itl; it != itr; ++it)
ans = (ans + pow(it->v, x, y)*(it->r - it->l + 1) % y) % y;
return ans;
}
signed main() {
scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
for (int i = 1; i <= n; ++i) a[i] = (rnd() % vmax) + 1, s.insert(Node(i, i, a[i]));
int op, l, r, x, y;
for (int i = 1; i <= m; ++i) {
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", rnk(l, r, x));
} else {
printf("%lld\n", cal(l, r, x, y));
}
}
system("pause");
return 0;
}
2. 珂朵莉树例题
CF915E Physical Education Lessons
这一道题只需要用到 split 和 assign 函数，但是由于要求总和，所以要对 assign 进行一些修改。
struct Node {
int l, r;
mutable int v;
Node (int l, int r = 0, int v = 0) : l(l), r(r), v(v) {}
bool operator < (const Node &a) const {
return l < a.l;
}
};
set<Node> s;
set<Node>::iterator split(int pos) {
set<Node>::iterator it = s.lower_bound(Node(pos));
if (it != s.end() && it->l == pos) return it;
it --;
if (it->r < pos) return s.end();
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;
}
void assign(int l, int r, int x) {
set<Node>::iterator itr = split(r+1), itl = split(l);
for (set<Node>::iterator it = itl; it != itr; ++it)
cnt -= it->v * (it->r - it-> l + 1);
s.erase(itl, itr);
s.insert(Node(l, r, x));
cnt += x * (r-l+1);
}
int main() {
scanf("%d%d", &n, &q);
s.insert(Node(1, n, 1));
int l, r, k; cnt = n;
while (q -- ) {
scanf("%d%d%d", &l, &r, &k);
if (k == 1) assign(l, r, 0);
else assign(l, r, 1);
printf("%d\n", cnt);
}
return 0;
}