好Van的珂朵莉树

2023-11-04 23:08:16

珂朵莉树

珂朵莉树的主要操作是区间覆盖，即将区间\([l,r]\)全部染色为\(c\)。

EXAMPLE

EXAMPLE 1

给出一个长度为\(n\)的序列，一共\(q\)次询问，每次询问给出\(m\)个区间，求这些区间并集的权值和。

\(n \leq 10^5,\sum m \leq 10^5\)

SOLUTION 1

~~显然能用珂朵莉树做~~

珂朵莉树是一种基于std::set的暴力数据结构。

这个set维护若干区间，这些区间没有交集，且按左端点从小到大有序。

struct node {
    int l, r, c;
    int operator<(const node& a) const { return l < a.l; }
};
set<node> S;
typedef set<node>::iterator IT;

珂朵莉树的基本操作有两个：

split(pos)

这个操作把包含了\(pos\)位置的区间分成两段，分别为\([l,pos-1]\)和\([pos,r]\)，且返回\([pos,r]\)的指针。

写法也很简单：

IT split(int po) {
    IT it = S.lower_bound((node){po, -1, 0});
    if (it != S.end() && it->l == po) return it;
    --it;
    int l = it->l, r = it->r, c = it->c;
    S.erase(it);
    S.insert((node){l, po - 1, c});
    return S.insert((node){po, r, c}).first;
}

assign(l, r, c)

这个操作将被\([l,r]\)包含的区间全部删除，然后用颜色\(c\)覆盖区间\([l,r]\)。

代码：

void cover(int l, int r, int c) {
    IT itr = split(r + 1), itl = split(l);
    S.erase(itl, itr); //意思是删除[itl, itr)，注意左闭右开
    S.insert((node){l, r, c});
    reset(c, sum[r] - sum[l - 1]);
}

那么，对于上面那题，怎么用珂朵莉树解决？

对于每个询问，我们直接cover(l, r)，由于操作的是整个区间，答案的增减可以直接\(O(1)\)得到，代码只需要在上面的写法上变一下即可：

void cover(int l, int r, int c) {
    IT itr = split(r + 1), itl = split(l), it = itl;
    for (; it != itr; ++it) {
        //这里可以直接根据it的左右端点增减答案
    }
    S.erase(itl, itr);
    S.insert((node){l, r, c});
    reset(c, sum[r] - sum[l - 1]);
}

EXAMPLE 2

给出一个\(n\)个节点的树以及\(m\)条树上路径，共\(q\)个询问，每次询问\([l_i,r_i]\)这些路径的并的权值。

SOLUTION 2

先离线询问，把询问\([l,r]\)挂在\(r\)。从左往右扫时，我们把第\(i\)条路径上的每个点染色为\(i\)，然后遍历挂在\(i\)上的询问，设其左端点是\(l\)，那么颜色\(>=l\)的点都有贡献。

树链剖分后路径染色转化为区间问题，为了统计\(c>=l\)的贡献和，我们再使用树状数组维护，用珂朵莉树解决染色问题，这题就搞定了。

复杂度

如果被覆盖的区间毫无贡献，那么可以证明珂朵莉树复杂度是\(O(nlogn)\)的。

因为每次assign最多增加\(3\)个区间，每次增加是\(O(logn)\)的，删除区间是均摊\(O(logn)\)的，所以复杂度是\(O(nlogn)\)的。

又扩展技能树啦~

码农公寓