目录
0x00：介绍
1x00：思想
1x01：节点保存
1x02：核心操作 split
1x03：推平操作 assign
2x00：例题
2x01：CF896C
2x02：CF915E
3x00：总结
0x00 介绍
珂朵莉树（Chtholly Tree），又称 ODT（Old Driver Tree），一种数据结构，但似乎暴力到不能称之为数据结构。可以很好地骗分，在随机数据下十分有效，常用于将\([l, r]\) 赋值为 \(k\) 的时候，我们将这个操作称为推平操作
1x00 思想
前置芝士：set
主要的思想是将值相同的区间放在同一个节点里，保存在 set 中
时间复杂度为 \(O(n \log \log n)\)
1x01 节点保存
节点代码如下
struct Node{
int l, r;
mutable int val;
Node(int l, int r, int val) : l(l), r(r), val(val){}
bool operator < (const Node a) const{
return l < a.l;
}
};
set<Node> Chtholly;
这其中，mutable 十分成功地吸引了我们的注意力，mutable 意为「可变的」，因为在 set 中，所有的变量都是常量，若要修改某个值，需要取出再放回去，加上了 mutable，就可以突破这个限制，达到直接修改某个值的目的。
1x02 核心操作 split
这里先给出代码
auto split(int x)
{
auto it = Chtholly.lower_bound(Node(x, 0, 0));
if (it != Chtholly.end() && it -> l == x)return it;
it--;
if (it -> r < x)return Chtholly.end();
int l = it -> l, r = it -> r, val = it -> val;
Chtholly.erase(it);
Chtholly.insert(Node(l, x - 1, val));
return Chtholly.insert(Node(x, r, val)).first;
}
split 第一段代码是为了找出第一个 \(x \le l\) 的元素，如果这个元素的 \(l = x\) 时，直接返回找到的。
然后 it--， 若下一个元素的 \(r > x\)，那么返回 set 的结尾。
接下来就是将他拆分开来，拆分成 \([l,x)\) 和 \([x,r]\)，先删除原节点，再加入\([l,x)\) 和 \([x,r]\) 这两个新节点。
split 操作的意义在于它可以将这些序列 \([l,r]\) 的操作转换为 set 中 \([split(l),split(r+1))\)，的操作。
1x03 推平操作 assign
理解了上面的代码，这里就应该很好理解了吧
void assign(int l, int r, int val)
{
auto itl = split(l), itr = split(r + 1);
for (auto it = itl; it != itr; it++)it -> val = val;
}
2x00 例题
2x01 例题一 CF896C
2x01x01 分析
万物之源。
操作 1 为区间加，像推平操作那样类似的方式即可
操作 2 为推平，直接用
操作 3 为区间第 \(k\) 小，用数组保存下这个区间的节点，然后询问
操作 4 为区间所有数的 \(x\) 次方之和 \(\bmod \ y\)，用快速幂解决掉
2x01x02 代码
/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
// #pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define endl '\n'
using namespace std;
struct Node{
int l, r;
mutable int val;
Node(int l, int r, int val) : l(l), r(r), val(val){}
bool operator < (const Node a) const{
return l < a.l;
}
};
struct Rank{
int val, num;
Rank(int val, int num) : val(val), num(num){}
bool operator < (const Rank a) const{
return val < a.val;
}
};
set<Node> Chtholly;
vector<Rank> RK;
auto split(int x)
{
auto it = Chtholly.lower_bound(Node(x, 0, 0));
if (it != Chtholly.end() && it -> l == x)return it;
it--;
if (it -> r < x)return Chtholly.end();
int l = it -> l, r = it -> r, val = it -> val;
Chtholly.erase(it);
Chtholly.insert(Node(l, x - 1, val));
return Chtholly.insert(Node(x, r, val)).first;
}
void assign(int l, int r, int val)
{
auto itr = split(r + 1), itl = split(l);
Chtholly.erase(itl, itr);
Chtholly.insert(Node(l, r, val));
}
void add(int l, int r, int val)
{
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)it -> val += val;
}
int rk(int l, int r, int x)
{
RK.clear();
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)
RK.push_back(Rank(it -> val, it -> r - it -> l + 1));
sort(RK.begin(), RK.end());
for (auto it = RK.begin(); it != RK.end(); it++)
if (x > it -> num)x -= it -> num;
else return it -> val;
return INF;
}
int qpow(int n, int k, int mod)
{
int res = 1, rhs = n % mod;
for (; k; k >>= 1, rhs = (rhs * rhs) % mod)
if (k & 1)res = (res * rhs) % mod;
return res;
}
int query(int l, int r, int x, int mod)
{
auto itr = split(r + 1), itl = split(l);
int res = 0;
for (auto it = itl; it != itr; it++)
res = (res + (it -> r - it -> l + 1) * qpow(it -> val, x, mod)) % mod;
return res;
}
int n, T, seed, mx, qwq;
int rnd()
{
int res = seed;
seed = (seed * 7 + 13) % (int)(1e9 + 7);
return res;
}
signed main()
{
#ifdef Fileopen
freopen(".in", r, stdin);
freopen(".out", w, stdout);
#endif
cin >> n >> T >> seed >> mx;
FOR(i, 1, n)Chtholly.insert(Node(i, i, (rnd() % mx) + 1));
while (T--)
{
int opt = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, mod;
if (l > r)swap(l, r);
if (opt == 3)x = (rnd() % (r - l + 1)) + 1;
else x = (rnd() % mx) + 1;
if (opt == 4)mod = (rnd() % mx) + 1;
if (opt == 1)add(l, r, x);
else if (opt == 2)assign(l, r, x);
else if (opt == 3)cout << rk(l, r, x) << endl;
else cout << query(l, r, x, mod) << endl;
}
return 0;
}
2x02 例题二 CF915E
2x02x01 分析
操作 1 和 2 都为推平操作，设非工作日为 0， 工作日为 1，那么就与上面的推平操作一样了，注意此题有一点卡常
2x02x02 代码
/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
// #pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define endl '\n'
using namespace std;
struct Node{
int l, r, val;
Node(int l, int r, int val) : l(l), r(r), val(val){}
bool operator < (const Node a) const{
return l < a.l;
}
};
set<Node> Chtholly;
auto split(int x)
{
auto it = Chtholly.lower_bound(Node{x, 0, 0});
if (it != Chtholly.end() && it -> l == x)return it;
it--;
if (it -> r < x)return Chtholly.end();
int l = it -> l, r = it -> r, val = it -> val;
Chtholly.erase(it);
Chtholly.insert(Node(l, x - 1, val));
return Chtholly.insert(Node{x, r, val}).first;
}
int n, T, sum;
void assign(int l, int r, int val)
{
auto itr = split(r + 1), itl = split(l);
for (auto it = itl; it != itr; it++)sum -= (it -> r - it -> l + 1) * it -> val;
Chtholly.erase(itl, itr);
Chtholly.insert(Node(l, r, val));
sum += val * (r - l + 1);
}
signed main()
{
#ifdef Fileopen
freopen(".in", r, stdin);
freopen(".out", w, stdout);
#endif
cin >> n >> T; sum = n;
Chtholly.insert(Node(1, n, 1));
while (T--)
{
int opt, l, r;
cin >> l >> r >> opt;
assign(l, r, opt - 1);
cout << sum << endl;
}
return 0;
}
3x00 总结
珂朵莉树是骗分好手，有推平操作都可以达到骗分的目的，若数据随机甚至会 AC
标签：Node,学习,return,val,Chtholly,int,笔记,朵莉树,split From： https://www.cnblogs.com/Manipula/p/17909472.html