填坑
珂朵莉树学习笔记
前言
我就是喜欢这种暴力的数据结构,打着就一个字,爽!
话说,滕老师告诉我别拿平衡树水线段树了...这是人话吗。
通过 这个题 我 get 到了珂朵莉树的基本操作,实在是佩服数据结构大师 lxl
PS: 珂朵莉树为啥叫作树,因为set内部是红黑树...
思想
就是一个暴力的思想,因为随机数据下assign会有四分之一,所以时间复杂度几乎是 \(O(m \log n)\) 的, 在std::set里存节点,每个节点就是一个区间,这个区间里的值都一样.话说看到 CF896C 的记录中 Falldream 用线段树搞出来了 %%%
正文
首先给出节点定义
struct Node { int l, r; mutable long long val; Node(int l, int r, long long Val) { this->l = l; this->r = r; this->val = Val; } bool operator < (const Node &x) const { return this->l < x.l; } };
其中 l, r 是这个区间的左右端点均是闭的,然后为啥用mutble关键字,因为通常你用了 set 模板库,他的数据结构会对里边的东西保护起来,所以要用可变的
初始化:
For(i, 1, n) s.insert(Node(i, i, rad() % vmax + 1)); s.insert(Node(n + 1, n + 1, 0));
这个初始化到也是我想了很久,在下文的split操作里会重点说。
split 函数
sst split(int pos) { sst it = s.lower_bound(Node(pos, 0, 0)); if(it != s.end() && it->l == pos) return it; --it; int l = it->l, r = it->r; long long v = it->val; s.erase(it); s.insert(Node(l, pos - 1, v)); return s.insert(Node(pos, r, v)).first; }
这个函数可是有点意思。我在前边为啥要插一个 \(n + 1\) 的节点 因为要是最后一个是个整段那不就凉凉了吗,我就因为这个 WA 了无数次..
然后相信有了这个思想之后就 ok 好多了
嵬
好像真的没啥要讲的,暴力数据结构需要讲?那玩意意会一个然后不就能写了吗...话说分块真的是有意思,有时间写写那个(前提是一模别炸,要是炸了我就投身到语文的怀抱里了)