珂朵莉树

notes

概述

set 维护连续段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct ADJ{ int l,r; mutable ll v; };
inline bool operator<(const ADJ &x,const ADJ &y){ return x.l<y.l; }
set<ADJ> s;

auto spl(int x){
	auto it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x) return it;
	auto [l,r,v]=*--it;
	s.erase(it),s.insert({l,x-1,v});
	return s.insert({x,r,v}).fi;
}
void cov(int l,int r,int v){
	auto itr=spl(r+1),itl=spl(l);
	s.erase(itl,itr),s.insert({l,r,v});
}
void add(int l,int r,int v){
	auto itr=spl(r+1),itl=spl(l);
	for(;itl!=itr;++itl){
        //...
    }
}

  • mutable 表示 $v$ 是可变的。

  • spl，将包含 $x$ 的区间 $[l,r]$，分裂成 $[l,x-1],[x,r]$，并返回 $[x,r]$ 对应的迭代器。

  • s.erase(itl,itr) 删除 $[itl,itr)$ 的元素。

  • s.insert() 返回一个 pair，first 是迭代器，second 是是否成功。

  • cov 时先右再左。

若操作后立刻区间赋值，那么时间复杂度 $O(n\log n)$。若操作是随机的，那么时间复杂度 $O(n\log \log n)$。

例题

  1. CF896C Willem, Chtholly and Seniorious

  2. P7912 [CSP-J 2021] 小熊的果篮

    链表维护连通块即可，时间复杂度均摊 $O(n)$。

  3. CF444C DZY Loves Colors

    可以势能线段树，或者珂朵莉树 + 区间加区间求和。

  4. P5251 [LnOI2019] 第二代图灵机

    操作三可以双指针，操作四也可以双指针。

  5. P4690 [Ynoi Easy Round 2016] 镜中的昆虫

    不修改就是求出 $pre_i$ 然后扫描线。

    单点修改可以 cdq 分治。

    区间修改发现 $pre$ 的总变化量为 $O(n)$，也可以 cdq 分治。

    这题这么 nb，🤡 了。

参考