暴力数据结构-珂朵莉树(ODT)

暴力数据结构-珂朵莉树(ODT)

珂朵莉001

(图片来自哔哩哔哩

介绍

珂朵莉树(Chtholly Tree,又称Old Driver Tree(ODT)),据说来源于CF896C,此题要求支持下列操作:

  • 区间加
  • 区间赋值
  • 求区间第 $k$ 小值
  • 求区间 $n$ 次方和

看上去似乎普通的数据结构如线段树、平衡树等无法处理,需要一种巧妙复杂的数据结构。但出题人(@lxl)的题解中所实现的却是一种十分暴力的数据结构,后来称作珂朵莉树。

适用条件

一般用于具有区间赋值且数据随机的题目。在随机数据的情况下,其时间复杂度可以达到 $O(n \log \log n)$ (证明)。

算法实现

初始化:

珂朵莉树以三元组 $$ 的方式储存数据,表示区间 $[L,R]$ 中的数的值均为 $V$。

1
2
3
4
5
6
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 &b) const {return L<b.L;}//重载小于运算符
};

注意 $V$ 的前缀 mutable,意为“可变的”,当整个结构体为const时,由它修饰的成员标仍然可以修改。

set 储存这些三元组:

1
set <Node> T;

这样,插入、查询、修改的时间就均为 $O(\log n)$ 啦。(当然,你也可以自己写以个平衡树QAQ)

核心操作:
  • $\operatorname{Split}$

$\operatorname{Split}$ 操作是将一个区间分裂为两个区间:

1
2
3
4
5
6
7
8
9
10
11
#define Auto set <Node> :: iterator //如果支持c++11,可以直接使用auto
Auto Split(int Pos) {
Auto it= T.lower_bound(Node(Pos,0,0));//找到第一个L不小于Pos的区间
if(it!=T.end() && it->L==Pos) return it;//如果不需要Split,就直接返回
--it;//找到Pos所在的区间
int L=it->L,R=it->R,V=it->V;
T.erase(it),T.insert(Node(L,Pos-1,V));
return T.insert(Node(Pos,R,V)).first;
//删除原区间,插入两个新分裂的区间,返回后插入的区间
//这里利用了pair<iterator,bool> insert (const value_type& val)的返回值
}
  • $\operatorname{Assign}$

$\operatorname{Assign}$ 函数是珂朵莉树保证其复杂度的核心,即区间赋值函数:

1
2
3
4
5
6
void Assign(int L,int R,int V) {
Auto itR=Split(R+1),itL=Split(L);
//值得注意的是,此处顺序不能颠倒,否则可能RE
//因为若先Split(L),那么Split(R)有可能使itL所指向的区间分裂,则删除itL~itR时会出错
T.erase(itL,itR),T.insert(Node(L,R,V));//消除范围内的所有区间,再插入合并后的区间
}

由于数据随机,会有大量的区间赋值操作,这样会迅速的缩小 $\operatorname{set}$ 的大小,保证其复杂度。

其他操作:(暴力大法好)
  • 区间加法:

一个一个加 Σ(っ°Д°;)っ

1
2
3
4
void Add(int L,int R,int V) {
Auto itR=Split(R+1),itL=Split(L);
for(; itL!=itR; ++itL) itL->V+=V;
}
  • 求区间第 $k$ 小值

暴力取出并排序 !!!∑(゚Д゚ノ)ノ

1
2
3
4
5
6
7
8
9
10
11
int Rank(int L,int R,int K) {
vector <pair<int,int> > Temp;
Auto itR=Split(R+1),itL=Split(L);
Temp.clear();
for(; itL!=itR; ++itL) Temp.push_back(pair<ll,ll>(itL->V,itL->R-itL->L+1));
sort(Temp.begin(),Temp.end());
for(vector <pair<int,int> > :: iterator it=Temp.begin(); it!=Temp.end(); ++it) {
K-=it->second;
if(K<=0) return it->first;
}
}
  • 求区间 $n$ 次方和

暴力遍历并快速幂 (°Д°)

1
2
3
4
5
6
int Sum(int L,int R,int Ex,int Mod) {
Auto itR=Split(R+1),itL=Split(L);
int reg=0;
for(; itL!=itR; ++itL) reg=(reg+(itL->R-itL->L+1)*Pow(itL->V,Ex,Mod))%Mod;
return reg;
}

例题

曾经有很多数据结构题可以用珂朵莉树水过,但被几个毒瘤(@noip @mrsrz @NaCly_Fish)给Hack了

总结

珂朵莉树是随机数据下表现良好的数据结构,但在非随机数据下极易被Hack,因此一般情况下只作为骗分或对拍使用。

发明者的blog

本文标题:暴力数据结构-珂朵莉树(ODT)

文章作者:Mchase

发布时间:2020年04月18日 - 17:09:17

最后更新:2022年07月29日 - 10:54:39

原始链接:http://yoursite.com/2020/%E6%9A%B4%E5%8A%9B%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E7%8F%82%E6%9C%B5%E8%8E%89%E6%A0%91-ODT/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。