珂朵莉树 ODT
主要内容
珂朵莉树是基于
数据随机且有整体赋值操作
而对序列操作的乱搞算法。
它的主要思想是用
set
维护若干个数值上相同的区间，并暴力处理其他询问。
建立
在
set
中，我们需要用结构体记录每个区间的信息：
struct NODE
{
int l,r;
mutable ll val; // mutable 表示可变的，便于在外边修改 val 的值
NODE(int L,int R=-1,ll Val=0):l(L),r(R),val(Vol){} // 相当于 (NODE){l,r,val}
bool friend operator < (NODE x,NODE y) { return x.l<y.l; } // 重载 <
};
set<NODE> s;
这样再
set
中就可以自动按照左端点排序了，注意在初始化的时候加入
\([n+1,n+1]\)
的区间。
split
珂朵莉树用
split
操作分裂出一堆区间后暴力操作。
inline auto split(int p)
{
auto it=s.lower_bound(NODE(p));
if(it!=s.end() && it->l==p) return it;
it--;
int l=it->l,r=it->r;
ll v=it->val;
s.erase(it);
s.insert(NODE(l,p-1,v));
return s.insert(NODE(p,r,v)).fi;
}
assign
如果只有
split
操作那
set
中元素岂不是爆炸？我们需要时不时将一些区间合并为一个区间才能保证复杂度。
\(\bigstar\texttt{attention}\)
：在推平的时候需要先
split
右端点再左端点，否则会 RE！
inline void assign(int l,int r,int v)
{
auto itr=s.split(r+1),itl=s.split(l);
s.erase(itl,itr); // 用将 [itl,itr) 之间的元素全部删除
s.insert(NODE(l,r,v));
}
其他操作
其他操作就可以直接暴力在
set
中搞了，下面以求区间内每个数的平方的和为例：
inline ll query(int l,int r)
{
auto itr=s.split(r+1),itl=s.split(l);
ll ret=0;
for(auto it=itl;it!=itr;it++)
ret+=1ll*(it->r-it->l+1)*it->v*it->v;
return ret;
}
复杂度
如果只有推平操作，即不需要将这个区间拎出来暴力处理，复杂度是
\(\mathcal{O(n\log n)}\)
。
如果有区间加等操作，就要基于数据随机了，这种情况下一定时间内进行一次推平可以达到
\(\mathcal{O(m\log n)}\)
的复杂度。
例题
起源题：
CF896C Willem, Chtholly and Seniorious
。
CF1638E Colorful Operations
在询问的时候把答案累加上去
，再套上一个树状数组利用前缀和维护区间加即可。
CF1423G Growing flowers
给你一个序列，支持以下两种操作：
- 区间推平，即将
\([l,r]\)
中的数都改为同一个数
\(x\)
。- 求序列中所有长度为
\(k\)
的子段中不同数的个数的和。
\(n,q\le 10^5\)
。
MatrixCascade：这题 800。
区间推平，所以考虑珂朵莉树。发现如果每次询问的时候再去统计，复杂度至少是和区间个数同阶，不可取。
考虑在推平的过程中更新答案。
将即将被推平的区间拎出来，将他们对答案减小的贡献减去。
对每一种数建立一个
set
，再用线段树记录方案数即可。