珂朵莉是什么？

以下內(nèi)容來(lái)自 \(oi-wiki\)

珂朵莉樹(shù)（Chtholly Tree），又名老司機(jī)樹(shù)

ODT（Old Driver Tree）。起源自 CF896C。

這個(gè)名稱(chēng)指代的是一種「使用平衡樹(shù)（std::set、std::map 等）或鏈表（std::list、手寫(xiě)鏈表等）維護(hù)顏色段均攤」的技巧，而不是一種特定的數(shù)據(jù)結(jié)構(gòu)。其核心思想是將值相同的一段區(qū)間合并成一個(gè)結(jié)點(diǎn)處理。相較于傳統(tǒng)的線段樹(shù)等數(shù)據(jù)結(jié)構(gòu)，對(duì)于含有區(qū)間覆蓋的操作的問(wèn)題，珂朵莉樹(shù)可以更加方便地維護(hù)每個(gè)被覆蓋區(qū)間的值。

珂朵莉雖然是一種優(yōu)化，但其本質(zhì)是一種均攤時(shí)間復(fù)雜度的思想，是比較看臉看人品的看數(shù)據(jù)隨機(jī)不隨機(jī)的，所以，如果不是實(shí)在不行了，想沖一把，請(qǐng)勿打 \(odt\) !

有多少種珂朵莉

有用 \(set\),\(map\) 維護(hù)的珂朵莉，也有用手打鏈表來(lái)維護(hù)的珂朵莉，這里三個(gè)都會(huì)提及，但是著重寫(xiě)用 \(set\) 維護(hù)的。

珂朵莉：set

珂朵莉的操作有哪些？

一.構(gòu)建

struct node 
{
    int l, r;
    mutable int v;
    node(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
    bool operator<(const node &o) const 
    {
        return l < o.l; 
    }
};

這是珂朵莉樹(shù)一個(gè)葉子的結(jié)構(gòu)，整顆珂朵莉用 \(set<node>\) 來(lái)維護(hù)，當(dāng)你要初始化時(shí)，在 \(set\) 中插入 \([1, n +1]\) 即可(或者是任意一個(gè)極長(zhǎng)區(qū)間也可以)。

二.split

\(split\) 可是珂朵莉的核心，但是這個(gè)核心真的沒(méi)什么不好理解的地方....

這個(gè)函數(shù)就是可以將一個(gè)區(qū)間 \([l, r]\) 劃分成 \([l,x)\) 和 \([x, r]\)。

代碼如下：

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

三.assign

另外一個(gè)重要的操作：assign。用于對(duì)一段區(qū)間進(jìn)行賦值。設(shè)將要對(duì)區(qū)間 \([l,r]\) 賦值為 \(v\)。

首先，將區(qū)間 \([l, r]\) 截取出來(lái)。依次調(diào)用 split(r + 1), split(l)，將此兩者返回的迭代器記作 \(itr, itl\)，那么 \([itl, itr)\) 這個(gè)迭代器范圍就指向了珂朵莉樹(shù)中 \([l,r]\) 包含的所有區(qū)間。

然后，將原有的信息刪除。std::set 有成員方法 erase，簽名如同 iterator erase( const_iterator first, const_iterator last );，可以移除范圍 [first; last) 中的元素。于是我們調(diào)用 odt.erase(itl, itr); 以刪除原有的信息。

最后，插入?yún)^(qū)間 \([l,r]\) 的新值。調(diào)用 odt.insert(Node_t(l, r, v)) 即可。

下面是代碼：

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

四.perform

就是將珂朵莉樹(shù)上的一段區(qū)間提取出來(lái)并進(jìn)行操作，其實(shí)只要把刪除區(qū)間改為遍歷區(qū)間即可。

代碼和上面一樣啦。

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

珂朵莉：map

差異

相較于 \(std::set\) 的實(shí)現(xiàn)，\(std::map\) 的實(shí)現(xiàn)的 \(split\) 操作寫(xiě)法更簡(jiǎn)單。除此之外，其余操作與 \(std::set\) 并無(wú)二異。

由于珂朵莉樹(shù)存儲(chǔ)的區(qū)間是連續(xù)的，我們不一定要記下右端點(diǎn)是什么。不妨使用一個(gè) map<int, int> mp; 存儲(chǔ)所有區(qū)間，其鍵維護(hù)左端點(diǎn)，其值維護(hù)其對(duì)應(yīng)的左端點(diǎn)到下一個(gè)左端點(diǎn)之前的值。

初始化時(shí)，如題目要求維護(hù)位置 \(1\) 到 \(n\) 的信息，則調(diào)用 \(mp[1] = -1, mp[n + 1] = -1\) 表示將 \([1, n + 1)\) 即 \([1, n]\) 都設(shè)為特殊值 \(-1\) (這里都是整數(shù)哈)，\([n+1, +\infty)\) 這個(gè)區(qū)間當(dāng)作哨兵使用，也可以對(duì)它進(jìn)行初始化。

剩下的就不細(xì)說(shuō)了哈，詳見(jiàn)代碼：

//F1:
void split(int x) 
{
    auto it = prev(mp.upper_bound(x)); 
    mp[x] = it->second; 
}
//F2:
auto split(int pos)
{
    auto it = prev(mp.upper_bound(pos)); 
    return mp.insert(it, make_pair(pos, it -> second));
}

void assign(int l, int r, int v) 
{
    split(l);
    split(r);
    auto it = mp.find(l);
    while(it -> first != r) it = mp.erase(it);
    mp[l] = v;
}

void perform(int l, int r)
{ 
    split(l);
    split(r);
    auto it = mp.find(l);
    while(it -> first != r) it = next(it);
}

珂朵莉：鏈表

太難寫(xiě)了，不寫(xiě)了，詳見(jiàn) oi-wiki, 反正我打死也不會(huì)寫(xiě)這個(gè)

題單

\(QwQ\)