区间的线段并&珂朵莉树

问题是这样的，一个序列，每个序列的元素是一条线段，给定做右端点\(l_i,r_i\)，然后询问\(L,R\)中\(\cup [l_i, r_i]\)的大小。加强版

介绍这个问题之前先说珂朵莉树。
我认为珂朵莉树的操作就是在区间上，把连续的，权值相同的点当作一个结点，然后不断的拆线段，合线段的过程（注意线段都是连续的），复杂度的话不会证（。用处多用来骗分啥的，但是也能解决上述问题。

珂朵莉树节点的存法如下：

struct Node{
    ll l, r;// 权值相同的区间是[l,r]
    int t;// 其他的量
    mutable ll v;// 权值
    bool operator < (const Node& tmp) const {
        return l < tmp.l;
    }
};

因为后面的操作影响，节点用 set维护set<Node> odt
基本操作分为两种，一个是分裂线段，\(split(x)\)表示把包含\(x\)的节点\([l,r]\)分裂成\([l,x-1],[x,r]\)。写法就是：

auto split(int x) {
    auto it = odt.lower_bound({x, 0, 0});
    if(it != odt.end() && it->l == x) return it;
    it --;
    int l = it->l, r = it->r, t = it->t;
    ll v = it->v;
    odt.erase(it);
    odt.insert({l, x - 1, t, v});
    return odt.insert({x, r, t, v}).first;
}

另外一个是给区间赋值，把\([l,r]\)的权值都赋成\(v\)。就是先把原来有\(l,r\)之间的点都删掉，如果不是整块区间的话就先分裂，然后加入\((l,r,v)\)这个点。写法：

void assign(ll l, ll r, ll v, int t) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.insert({l, r, t, v});
}

注意，必须先\(split(r+1)\)，因为如果先\(split(l)\)在\(split(r+1)\)可能会导致\(itl\)被删除，就是\(split(l)\)后\(l\)和\(r\)还在一个块，此时删\(r\)就会先把\(itl\)先删了，再新建两个节点。
基本操作就没了，这道题也够用了，然后更多的操作详见OI Wiki

这道题怎么维护呢，可以类似HH 的项链就是把权值放到最近更改的地方贡献，对于这道题来说，就是先把询问离线，然后扫描区间的右端点，再维护一个树状数组，里面的\(i\)表示\([1,r]\)中的线段最后一次贡献答案是在\(i\)，询问就是查询树状数组\([L,R]\)之间的权值。在\(set.erase\)的时候把原来的贡献删掉就行。然后没了。

复杂度\(O(n\log n)\)，证明见OI Wiki