YrainyQWQ's blogs

介绍 珂朵莉树（Chtholly Tree），又称 ODT（Old Driver Tree），一种数据结构，但似乎暴力到不能称之为数据结构。可以很好地骗分，在随机数据下十分有效，常用于将[l,r][l, r][l,r] 赋值为 kkk 的时候，我们将这个操作称为推平操作 思想 前置芝士：set 主要的思想是将值相同的区间放在同一个节点里，保存在 set 中 时间复杂度为 O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn) 节点保存 节点代码如下 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 中，所有的变量都是常量，若要 ...

分块简介 分块，其实不是数据结构，是一种思想，但常用于数据结构中，所以通常把分块当作数据结构来看待。 分块的主要思想就是将一段数列分为 n\sqrt{n}n​ 块，进行修改和查询操作，有着 O(nn)O(n \sqrt{n})O(nn​) 的时间复杂度。虽然效率不如线段树和树状数组的 O(nlog⁡n)O(n \log{n})O(nlogn)，但比线段数更好调，也是它的一大优点。 算法简述 一开始先预处理出每个点所在块，一些可以自行加，比如某个块的左端点和右端点。 先讲修改操作。 修改操作 我们可以讲序列分为 O(n)O(\sqrt{n})O(n​) 块，然后可以分为 左端点所在块\color{blue}\text{左端点所在块}左端点所在块，右端点所在块\color{blue}\text{右端点所在块}右端点所在块 和 两个块之间包着的块\color{red}\text{两个块之间包着的块}两个块之间包着的块。 对于两个块之间包着的块，一个一个块进行修改，对于左端点和右端点所在块，直接暴力修改即可。 至于为什么要分为 O(n)O(\sqrt{n})O(n​) 块，是因为根号平衡 ...