[珂學の暴力]ODT / Chtholly Tree

0x00 Prologue

最近閑下來了...刷CF的時候奇奇怪怪地刷到了珂朵莉round(Codeforces Round #449 (Div. 1))。裡面的題可以說是非(shí)常(fēn)奈(dú)斯(liú)了。其中有一道題很有趣——CF896C(洛谷)。寫一個數據結構，支持以下4個操作

• 將區間 中的所有數加上
• 將區間 中的所有數改成 （這個是ODT優勢體現的操作）
• 輸出區間 中第 大的數
• 輸出 ，即 區間內元素的 次冪和

數據隨機！

對於這類有區間推平操作數據又隨機的題，ODT就十分適用了

UPD @ 04 / 29 / 18 04:33 p.m.

（julao @Guanghao Ye來批判了：老司機樹原版是lxl搞的！老司機樹原版是lxl搞的！老司機樹原版是lxl搞的！）。

~~老司機擅長推車，珂朵莉擅長推平區間！~~

本文將以這道題作為例子講解Old Driver Tree / 珂朵莉樹的智慧 / 暴力美學。

0x01 如何維護？

珂朵莉樹將區間信息以三元組的形式存儲，即用 表示 中的元素為 。從這裡就能看出為什麼珂朵莉樹對於區間推平較為高效了。我們用set存儲這些三元組，內部維護這些區間，以左端點 作為關鍵字進行升序排列，這樣方便我們進行一些操作的時候方便查找到我們想要修改的區間。區間節點結構如下：

struct Node { int l, r; mutable ll v; // 在用迭代器訪問時能夠修改值 Node(){} Node(int L, int R=-1, LL V=0l): l(L), r(R), v(V){} bool operator < (const Node& b) const { return l < b.l; }};

一些操作？不不不，其實核心操作只有一個：split(p)——將 所在區間拆分為 和 。

由於在set中的所有節點是有序的，我們可以用lower_bound(x)定位我們要操作的區間。（注: lower_bound(x)可以在$logn$時間內在一個有序序列中找到最小的 使得 並返回 的位置 / 迭代器，一個二分查找的過程）

這時我們要分以下兩種情況處理通過 找到的區間：

• 如果 已經是某個區間的左端點，那麼我們直接返回查找到的迭代器;
• 如果 不是某個區間的左端點，那麼當前返回的迭代器所指向的區間是 所在區間右邊第一個區間。這時將迭代器後移一位。如果在後移之後， 比當前區間的右端點還大，那麼直接返回尾迭代器(因為不需要進行操作)；否則 ，那麼記錄一下當前區間的信息，然後直接刪除當前區間再插入拆分好的區間 和 ，最後返回 所在區間的迭代器(操作只會影響包含 的區間)。

inline set<Node>::iterator split(int p) { auto it = s.lower_bound(Node(p)); if(it != s.end() && it->l == p) return it; // 情況一 --it; // 找到p所在區間 if(it->r < p) return s.end(); // 不需要拆分 int L = it->l, R=it->r; // 記錄信息 LL v = it->v; s.erase(it); s.insert(Node(L, p - 1, v)); // 插入新區間 return s.insert(Node(p, R, v)).first;}

0x02 實現操作

1. 區間賦值

有了split之後，我們就能利用split做各種神(bao)奇(li)的操作了。先來看一個區間賦值的操作。

現在給定了我們 , 和 。首先為了能夠暴力，我們先把 和 所在區間各自拆分出來。既然我們是區間賦值(推平)，我們可以直接將 從set中移除再添加一個新的 區間，其中的值為 :

inline void modify(int l,int r,int v) { auto R=split(r+1), L = split(l); s.erase(L, R); s.insert(Node(l, r, v)); return;}

在這個操作的過程中會有許多小區間被合併到 ，因此空間複雜度會大大減小。

2. 區間加

第一步與區間賦值一樣，首先拆分 和 。之後，我們直接暴力修改 中的值，由於數據隨機，所以複雜度並不會爆時間。

inline void add(int l, int r, int v) { auto R = split(r+1), L=split(l); while(L != R) { L->v += v; ++L; } return;}

區間$k$次冪和與區間加操作十分類似，大家可以嘗試寫一個。

3. 區間第 大

這纔是真正的暴力。第一步依舊是拆分 與 。然後我們將 中所有區間拿出來，將區間長度和區間值存到pair，放到vector裏，然後對其中所有區間按照 升序排列。然後遍歷vector，每次將 減去當前區間長度，直到 。十分的暴力，但是由於數據隨機和區間合併時導致區間數量減少，我們依舊能過題。

inline ll kth(int l, int r,int k) { auto R = split(r+1), L = split(l); vector<pii> vec; while(L != R) { vec.push_back(make_pair(L->v, L->r - L->l + 1)); ++L; } sort(vec.begin(), vec.end(), [=](pii a, pii b) -> bool { return a.first < b.first; }); for(auto i: vec) { k -= i.second; if(k <= 0) return i.first; } return -1;}

0x03 注意事項

雖然ODT / 珂朵莉樹寫起來十分容易，並且十分暴力，但是這個數據結構有一些使用上的限制：

• 適用於有區間推平 / 覆蓋操作的
• 數據是隨機的

數據隨機很重要，因為如果推平區間操作很少 / 很多單點，珂朵莉會被卡掉呀QwQ

0x04 Epilogue

在知乎寫了一半不知道為什麼草稿沒有保存，打開之後是空的…是空的！！！心態崩了呀，於是我重新寫了大半篇TuT。繼續刷CF準備10月校賽….