[珂學の暴力]ODT / Chtholly Tree

0x00 Prologue

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

將區間中的所有數加上
將區間中的所有數改成（這個是ODT優勢體現的操作）
輸出區間中第大的數
輸出 $sum_{i=L}^{R}a_i^k$ ，即區間內元素的次冪和

數據隨機！

對於這類有區間推平操作數據又隨機的題，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;}