珂朵莉树
珂朵莉树 (ODT)
珂朵莉
我永远喜欢珂朵莉。
如果幸福有颜色，那一定是终末之红染尽的蓝色！
一个 dalao 的 图 。
萌娘百科：
珂朵莉树
珂朵莉树是基于 set 的暴 (pian) 力 (fen) 算法。
前置知识
优点
珂朵莉全身都是优点
码量小，思路清晰易查错。
应用范围
-
含推平操作，即将一个区间的数全部更新为相同的数。
-
数据随机（防止毒瘤出题人卡珂朵莉）。
基本思想
用 set 储存三元组 \((left,right,value)\) ，将部分连续相同的元素储存到一起。
核心
split 是整个 ODT 的核心操作。
因为三元组存的区间和每次操作维护的区间不一定完全相同，所以操作之前我们要将区间先分裂，然后再维护。
手模：
假设现在的珂树长这样：
\(\begin{array}{|c|c|c|c|} 1,3,4&4,5,7&6,14,2&15,15,2 \end{array}\)
接下来要将区间 \(5\sim10\) 推平为 \(-3\) 。
-
将区间 <4,5,7> 和 <6,14,2> 分裂成 <4,4,7>,<5,5,7>,<6,10,2>,<11,14,2> 。
-
将 <5,5,7> 和 <6,10,2> 删掉。
-
将 <5,10,-3> 加入。
此时的珂树长这样：
\(\begin{array}{|c|c|c|c|c|} 1,3,4&4,4,7&5,10,-3&11,14,2&15,15,2 \end{array}\)
这就是下面的分裂 (split) 和推平 (assign) 操作。
实现
- 结构体
只需要存 set 需要的三元组，然后用重载运算符，让 set 按照区间的左端点排序。
struct C_tree{
int le,ri;
mutable int val;
C_tree(int le,int ri=0,int val=0):
le(le),ri(ri),val(val){}
bool operator <(const C_tree &b)const
{
return l- 分裂
按手模的方法进行：
settre;
#define IT set::iterator
IT split(int now)
{
IT i=tre.lower_bound(Chtholly(now));
if(i!=tre.end()&&i->le==now)return i;
i--;int l=i->le,r=i->ri,v=i->val;
tre.erase(i);
tre.insert((Chtholly){l,now-1,v});
return tre.insert((Chtholly){now,r,v}).first;
}
关于 iterator 和 return .first ，都是有关 set 的使用，这里不再赘述。
- 推平
如果只分裂，那么 set 的大小就会增大直到达到 n ，此时我们再用 set 就会很慢。所以需要将一个区间推平。
void assign(int l,int r,int k)
{
IT ir=split(r+1),il=split(l);
tre.erase(il,ir);
tre.insert(C_tree(l,r,k));
}
- 暴力
用 set 维护好三元组之后，剩余的操作就基于 set 进行暴力维护就好了。
比如
- 区间加：
void update(int l,int r,int k)
{
IT ir=split(r+1),il=split(l);
while(il!=ir)
{
il->val+=k;
il++;
}
}
- 区间查值
typedef pairPr;
int ask_rank(int l,int r,int k)
{
vectorans_;
IT ir=split(r+1),il=split(l);
for(IT i=il;i!=ir;i++)
ans_.push_back((Pr){i->val,((i->ri)-(i->le)+1)});
sort(ans_.begin(),ans_.end());
vector::iterator i=ans_.begin();
while(i!=ans_.end())
{
k-=i->second;
if(k<=0)return i->first;
i++;
}
return -1;
}
- 区间次幂和
int ksm(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 ask_sum(int l,int r,int x,int y)
{
int ans=0;
IT ir=split(r+1),il=split(l);
for(IT i=il;i!=ir;i++)
ans=(ans+ksm(i->val,x,y)*(i->ri-i->le+1))%y;
return ans;
}
关于对适用条件的解释
-
含推平
没有推平操作会让
set的大小趋近甚至达到 \(O(n)\) 的级别，那么用珂朵莉树就会 T 到飞起。 -
数据随机
这样可以有较大概率将某段区间合并，从而将
set的大小急剧下降，使其大小稳定在 \(O(\log n)\) 的范围左右，而不像某些 毒瘤题目 (@ 序列操作 ) 将珂朵莉树卡的死死的。像这样：
话说，前三个点跑的还挺快。
例题
U191085
CF915E
CF558E
剩下的都是看似能用 ODT 实则都会被卡的题
P2572
P2787
P4344
P4979
P2894