演算法學習筆記: 珂朵莉樹
- 2020 年 8 月 4 日
- 筆記
- 演算法----------
珂朵莉樹（Chtholly Tree）起源於CF896C，那道題要求我們實現一種數據結構，可以較快地實現：
- 區間加
- 區間賦值
- 求區間第k大值
- 求區間n次方和
原題如下：
(CF896C Willem, Chtholly and Seniorious)
Seniorious is made by linking special talismans in particular order.
After over 500 years, the carillon is now in bad condition, so Willem decides to examine it thoroughly.
Seniorious has n pieces of talisman. Willem puts them in a line, the i-th of which is an integer ai.
In order to maintain it, Willem needs to perform m operations.
There are four types of operations:1 l r x: For each i such that l ≤ i ≤ r, assign ai + x to ai.
2 l r x: For each i such that l ≤ i ≤ r, assign x to ai.
3 l r x: Print the x-th smallest number in the index range [l, r], i.e. the element at the x-th position if all the elements ai such that l ≤ i ≤ r are taken and sorted into an array of non-decreasing integers. It’s guaranteed that 1 ≤ x ≤ r - l + 1.
4 l r x y: Print the sum of the x-th power of ai such that l ≤ i ≤ r, modulo y, i.e..
Input
The only line contains four integers n, m, seed, vmax (1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109).
The initial values and operations are generated using following pseudo code:def rnd():
ret = seed
seed = (seed * 7 + 13) mod 1000000007
return retfor i = 1 to n:
a[i] = (rnd() mod vmax) + 1
for i = 1 to m:
op = (rnd() mod 4) + 1
l = (rnd() mod n) + 1
r = (rnd() mod n) + 1if (l > r):
swap(l, r)if (op == 3):
x = (rnd() mod (r – l + 1)) + 1
else:
x = (rnd() mod vmax) + 1if (op == 4):
y = (rnd() mod vmax) + 1Here op is the type of the operation mentioned in the legend.
Output
For each operation of types 3 or 4, output a line containing the answer.
就此需求來說，普通的樹狀數組、線段樹等顯然難以勝任，看上去需要一種相當複雜的數據結構。然而，在這位珂學家出題人的題解中，他實現的數據結構卻很簡單，甚至看起來有點……暴力。他一開始用自己的id把這種數據結構命名為ODT，後又改而定名為珂朵莉樹。
珂朵莉樹的適用範圍是有區間賦值操作且數據隨機的題目。其實珂朵莉樹看上去並不像是樹狀數據結構，但因為一般要用到std::set，而std::set是用紅黑樹實現的，所以也不算名不副實。在隨機數據下，珂朵莉樹可以達到 的複雜度（參見這篇文章）。
珂朵莉樹的思想在於隨機數據下的區間賦值操作很可能讓大量元素變為同一個數。所以我們以三元組<l,r,v>的形式保存數據（區間 中的元素的值都是v）：
翻譯成程式碼：
struct node
{
ll l, r;
mutable ll v; // 這裡mutable要寫不然可能會CE
node(ll l, ll r, ll v) : l(l), r(r), v(v) {} // 構造函數
bool operator<(const node &o) const { return l < o.l; } // 重載小於運算符
};
然後把這些三元組存儲到set里（也可以用鏈表，但set更優秀）：
set<node> tree;
要把結構體放進set里需要重載小於運算符，set會保證內部元素有序（插入、刪除和查詢的時間複雜度都是 ）。而mutable使得當整個結構體為const時，標為mutable的成員仍可變（因為可能有區間加等操作）。
然而，我們進行區間操作時並不總是那麼幸運，可能會把原本連續的區間斷開。我們需要一個函數來實現「斷開」的操作，把<l,r,v>斷成<l,pos-1,v>和<pos,r,v>：
auto split(ll pos)
// 若不支援C++14，auto須改為set<node>::iterator
{
auto it = tree.lower_bound(node(pos, 0, 0)); // 尋找左端點大於等於pos的第一個節點
// 若不支援C++11，auto須改為set<node>::iterator
if (it != tree.end() && it->l == pos) // 如果已經存在以pos為左端點的節點，直接返回
return it;
it--; // 否則往前數一個節點
ll l = it->l, r = it->r, v = it->v;
tree.erase(it); // 刪除該節點
tree.insert(node(l, pos - 1, v)); // 插入<l,pos-1,v>和<pos,r,v>
return tree.insert(node(pos, r, v)).first; // 返回以pos開頭的那個節點的迭代器
// insert默認返回值是一個pair，第一個成員是我們要的
}
例如剛剛的情況，如果要split(4)會發生什麼？
再放一次圖免得往上滑
首先lower_bound，找到左端點大於等於4的節點，<5,6,3>。它的左端點不是4，所以回退，得<2,4,2>。我們把節點<2,4,2>刪除，然後插入<2,3,2>及<4,4,2>即可。是不是很簡單？
珂朵莉樹的精髓在於區間賦值。而區間賦值操作的寫法也極其簡單：
void assign(ll l, ll r, ll v)
{
auto end = split(r + 1), begin = split(l); // 順序不能顛倒，否則可能RE
tree.erase(begin, end); // 清除一系列節點
tree.insert(node(l, r, v)); // 插入新的節點
}
無非就是把範圍內的節點全部刪除，然後換上新的（範圍較大的）節點而已。只是需要注意求end和begin的順序不能顛倒，因為split(end)可能把begin原來所在的節點斷開。
到此為止，已經可以輕鬆A掉這道紫題了：
（CF915E Physical Education Lessons 洛谷@小粉兔譯）
Alex高中畢業了，他現在是大學新生。雖然他學習編程，但他還是要上體育課，這對他來說完全是一個意外。快要期末了，但是不幸的Alex的體育學分還是零蛋！
Alex可不希望被開除，他想知道到期末還有多少天的工作日，這樣他就能在這些日子裡修體育學分。但是在這裡計算工作日可不是件容易的事情：
從現在到學期結束還有天(從
到
個指令，每個指令可以用三個參數
描述：
如果，那麼從
到
（包含端點）的所有日子都變成非工作日。
如果，那麼從
到
（包含端點）的所有日子都變成工作日。
幫助Alex統計每個指令下發後，剩餘的工作日天數。
輸入格式
第一行一個整數，第二行一個整數
，分別是剩餘的天數和指令的個數。
接下來行有
個整數
，描述第
。
輸出格式
輸出個指令被下發後剩餘的工作日天數。
只需要在assign過程中求一下和即可，部分程式碼如下：
int sum;
void assign(int l, int r, int v)
{
int tot = 0, len = 0;
auto end = split(r + 1), it = split(l), begin = it;
for (it; it != end; it++)
{
len += (it->r - it->l + 1);
tot += it->v * (it->r - it->l + 1);
}
tree.erase(begin, end);
tree.insert(node(l, r, v));
if (v == 1)
sum += (len - tot);
else
sum -= tot;
}
int main()
{
int n = read(), q = read();
tree.insert(node(1, n, 1));
sum = n;
while (q--)
{
int l = read(), r = read(), k = read();
assign(l, r, k == 1 ? 0 : 1);
printf("%d\n", sum);
}
return 0;
}
那麼，文章開頭那些複雜的操作，要如何實現呢？實際上一點都不複雜，就兩個字，暴力。
區間加（就挨個加）：
void add(ll l, ll r, ll v)
{
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
it->v += v;
}
求區間k大值（直接扔到vector里排下序）：
ll kth(ll l, ll r, ll k)
{
auto end = split(r + 1);
vector<pair<ll, ll>> v; // 這個pair里存節點的值和區間長度
for (auto it = split(l); it != end; it++)
v.push_back(make_pair(it->v, it->r - it->l + 1));
sort(v.begin(), v.end()); // 直接按節點的值的大小排下序
for (int i = 0; i < v.size(); i++) // 然後挨個丟出來，直到丟出k個元素為止
{
k -= v[i].second;
if (k <= 0)
return v[i].first;
}
}
求區間n次方和（用快速冪直接求）：
ll sum_of_pow(ll l, ll r, ll x, ll y)
{
ll tot = 0;
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y; // qpow自己寫一下
return tot;
}
真是一個比一個暴力……然而因為隨機數據中大量賦值操作的存在，整個珂朵莉樹上也沒有太多節點，所以速度還是很可觀的。需要注意的是，如果題目不保證隨機數據，非常容易hack。所以很多時候，珂朵莉樹也許只能當作一種對拍方法或者騙分演算法。
（更新）但是……事實上，還有一種暴力+暴力法。就是，先把數據離線下來，然後，根據輸入數據的特點（比如有多少次大範圍的賦值），選擇直接暴力或使用珂朵莉樹。因為，如果一個數據具有卡珂朵莉樹的特點，那麼它肯定大範圍賦值較少，那麼暴力的複雜度也許就可以接受。
CF896C的完整程式碼如下（題目專門給了一個隨機數生成器就是防hack…）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll ans = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
ans = ans * 10 + c - '0';
c = getchar();
}
return ans;
}
struct node
{
ll l, r;
mutable ll v;
node(ll l, ll r, ll v) : l(l), r(r), v(v) {}
bool operator<(const node &o) const { return l < o.l; }
};
set<node> tree;
auto split(ll pos)
{
auto it = tree.lower_bound(node(pos, 0, 0));
if (it != tree.end() && it->l == pos)
return it;
it--;
ll l = it->l, r = it->r, v = it->v;
tree.erase(it);
tree.insert(node(l, pos - 1, v));
return tree.insert(node(pos, r, v)).first;
}
void assign(ll l, ll r, ll v)
{
auto end = split(r + 1), begin = split(l);
tree.erase(begin, end);
tree.insert(node(l, r, v));
}
ll qpow(ll a, ll n, ll p)
{
ll ans = 1;
a %= p;
while (n)
{
if (n & 1)
ans = ans * a % p;
n >>= 1;
a = a * a % p;
}
return ans;
}
ll n, m, seed, vmax;
ll rnd()
{
ll ret = seed;
seed = (seed * 7 + 13) % 1000000007;
return ret;
}
void add(ll l, ll r, ll v)
{
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
it->v += v;
}
ll kth(ll l, ll r, ll k)
{
auto end = split(r + 1);
vector<pair<ll, ll>> v;
for (auto it = split(l); it != end; it++)
v.push_back(make_pair(it->v, it->r - it->l + 1));
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
{
k -= v[i].second;
if (k <= 0)
return v[i].first;
}
}
ll sum_of_pow(ll l, ll r, ll x, ll y)
{
ll tot = 0;
auto end = split(r + 1);
for (auto it = split(l); it != end; it++)
tot = (tot + qpow(it->v, x, y) * (it->r - it->l + 1)) % y;
return tot;
}
int main()
{
n = read(), m = read(), seed = read(), vmax = read();
for (int i = 1; i <= n; ++i)
{
int r = rnd();
tree.insert(node(i, i, r % vmax + 1));
}
for (int i = 1; i <= m; ++i)
{
ll opr = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1, x, y;
if (l > r)
swap(l, r);
if (opr == 3)
x = rnd() % (r - l + 1) + 1;
else
x = rnd() % vmax + 1;
if (opr == 4)
y = rnd() % vmax + 1;
switch (opr)
{
case 1:
add(l, r, x);
break;
case 2:
assign(l, r, x);
break;
case 3:
printf("%lld\n", kth(l, r, x));
break;
case 4:
printf("%lld\n", sum_of_pow(l, r, x, y));
}
}
return 0;
}
最後附上一張世界上最幸福的女孩珂朵莉
