题前碎语
我为什么要在期考前写玄学数据结构的笔记……
我是不是有点大病……
huige说我在越级做题，但是StudyingFather的题解里说学会珂朵莉树只要会用std::set（
题目简介
CF896C Willem, Chtholly and Seniorious
CodeForces原题传送门
洛谷传送门
题目背景就不抄了，想看的珂学家可以直接去看原题。
题目描述
实现一个支持以下操作的数据结构：
- \(1\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数加上\(x\)
- \(2\) \(l\) \(r\) \(x\) ：将\([l,r]\) 区间所有数改成\(x\)
- \(3\) \(l\) \(r\) \(x\) ：输出将\([l,r]\) 区间从小到大排序后的第\(x\) 个数是的多少(即区间第\(x\) 小，数字大小相同算多次，保证 \(1\leq\) \(x\) \(\leq\) \(r-l+1\) )
- \(4\) \(l\) \(r\) \(x\) \(y\) ：输出\([l,r]\) 区间每个数字的\(x\) 次方的和模\(y\) 的值(即(\(\sum^r_{i=l}a_i^x\) ) \(\mod y\) )
输入格式
这道题目的输入格式比较特殊，需要选手通过\(seed\) 自己生成输入数据。
输入一行四个整数\(n,m,seed,v_{max}\) （\(1\leq\) \(n,m\leq 10^{5}\) ,\(0\leq seed \leq 10^{9}+7\) \(,1\leq vmax \leq 10^{9}\) ）
其中\(n\) 表示数列长度，\(m\) 表示操作次数，后面两个用于生成输入数据。
题目给出用于生成数据的伪代码如下：
def rnd():
ret = seed
seed = (seed * 7 + 13) mod 1000000007
return ret
for 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) + 1
if (l > r):
swap(l, r)
if (op == 3):
x = (rnd() mod (r - l + 1)) + 1
else:
x = (rnd() mod vmax) + 1
if (op == 4):
y = (rnd() mod vmax) + 1
输出格式
对于每个操作3和4，输出一行仅一个数。
这题需要实现的就是大名鼎鼎的珂朵莉树——\(Chtholly\) \(Tree\)(又叫\(Old\)-\(Driver\) \(Tree\),简称\(ODT\))。
不过根据各位大佬的解释，珂朵莉树实际上不能算是一种数据结构，而是一种暴力解决问题的算法技巧。
不管这么多，直接开始正题。
珂朵莉树最出众的功能就是推倒（hso）操作，把一个区间全部修改为同一个数，也就是这题的操作2。
当然，我们首先得写一个结构体，把每个区间的左端点、右端点和数值存起来。
struct odt {
ll left, right;
mutable ll val;
odt(ll left, ll right = 0, ll val = 0) : left(left), right(right), val(val) {}//初始化，当然强制转换也行
inline bool operator<(const odt &x) const {
return left < x.left;//按左端点排序
}
};
注意到对val的定义多了个mutable关键字，这个在之后的操作里有很大作用，暂且卖个关子。
接下来用一个set把点给存起来进行初始化。伪代码中给出的数据用a[i]表示，这里直接插进set里就好了，不需要这个数组。
std::set< odt > S;
for (int i = 1; i <= n; i++)
S.insert(odt(i, i, (rnd() % vmax) + 1));
很快，我们来到了珂朵莉树最为核心最为关键的一个函数：\(split\)!
（它是如此关键以至于我要用一个\(\LaTeX\)来强调）
这个函数的作用是把一个区间分割成\([left,pos-1]\)和\([pos,right]\)，这样才方便之后的合并；同时返回一个迭代器，代表后半段开头。
先定义一个迭代器表示不小于pos的点，然后分成以下几个情况看待：
- 如果这个区间以pos为起点，那就不需要做任何事，直接返回这个迭代器；
- 如果右端点比pos还要小，那就直接返回S.end()；
- 如果把pos包含上了，才需要把区间分成两半，顺便把原来那个区间删掉。
auto split(ll pos) {
auto it = S.lower_bound(odt(pos));
if (it != S.end() && (it -> left) == pos)//情况1
return it;
it--;
if ((it -> right) < pos)//情况2
return S.end();
ll l = it -> left, r = it -> right, v = it -> val;//情况3
S.erase(it);
S.insert(odt(l, pos - 1, v));
return S.insert(odt(pos, r, v)).first;
}
这里利用到了两个小技巧。
第一个是insert函数有返回值，是一个pair，并且这个pair的first就是我们需要的后半段开头的迭代器，所以直接返回。
第二个就是C++14的独门秘技——auto！！！
auto可以直接根据数据判定数据类型，这是一个很棒的东西。
试想一下，如果没有auto，写一个迭代器定义就只能是：
std::set< odt >::iterator
写起来又累又容易打错！
虽然我们可以用宏定义解决这个问题，但是auto就能轻松解决。
有人可能会问了：
auto不是C++11就有了吗？
确实，但是在C++11，auto不能作为函数返回值，这意味着我们的\(split\)只能回到那个冗长的样子。
更重要的是，在NOI-Linux 2.0里，C++14统一使用！！！
改革春风吹满地，用C++14的CCF真神气！
啊好像有点跑题了（
下一个要实现的就是推倒区间的操作——assign。
有了前面split的铺垫，这一步就灰常简单了~
定义两个迭代器代表区间左端点和右端点，用split把区间分解，然后插入推倒之后的新区间，并且用S.erase(it_l, it_r)删掉之前的区间。
需要注意的是，一定要先分解后半段再分解前半段，否则会访问到空区间导致RE。
void assign(ll l, ll r, ll v) {
auto it_r = split(r + 1), it_l = split(l);
S.erase(it_l, it_r);
S.insert(odt(l, r, v));
}
剩下的几个操作也都很简单，快点过掉吧~
全部加上一个数：
定义端点-遍历-直接加，简单粗暴。
void add(ll l, ll r, ll v) {
auto it_r = split(r + 1), it_l = split(l);
for (auto it = it_l; it != it_r; it++)
it->val += v;
}
前面提到的multable就是在这儿发挥作用的~
iterator是常量迭代器，正常情况下没法改数据，但是加上了multable就意味着常量也可以被强制修改，加数字就能轻松实现了~
查询区间第x小：
全部扔到一个vector里面排序，然后逐个相减，也很简单粗暴。
有的题解又定义一个结构体，其实用pair足矣：first代表数字，second代表相同数字的数量（有点像桶排序里的桶？）。
顺带一提，这个函数我一开始犯了各种各样的低级错误，还被huige说了一顿……qwq
ll rank(ll l, ll r, ll x) {
std::vector< std::pair<ll, ll> > V;
auto it_r = split(r + 1), it_l = split(l);
for (auto it = it_l; it != it_r; it++)
V.push_back(std::make_pair(it -> val, (it -> right) - (it -> left) + 1));
std::sort(V.begin(), V.end());
auto it = V.begin();
while (it != V.end() && it -> second < x)
x -= (it -> second),it++;
return it -> first;
}
不知道在干什么的申必操作求乘方和取模，同样很暴力。
小提醒：做快速幂的时候要先把底数模一下，因为有可能在a*a%p的时候爆long long导致结果错误。
ll calc(ll l, ll r, ll x, ll y) {
auto it_r = split(r + 1), it_l = split(l);
ll ans = 0;
for (auto it = it_l; it != it_r; ++it)
ans = (ans + qpow(it -> val, x, y) * ((it -> right) - (it -> left) + 1) % y) % y;
return ans;
}
好啦，所有操作实现完成，是时候祭出珂朵莉树的完整代码了！
#include <set>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
const ll mod = 1000000007;
ll n, m, seed, vmax;
struct odt {
ll left, right;
mutable ll val;
odt(ll left, ll right = 0, ll val = 0) : left(left), right(right), val(val) {}
inline bool operator<(const odt &x) const {
return left < x.left;
}
};
std::set< odt > S;
inline ll qpow(ll a, ll b, ll p) {
ll ans = 1;
a %= p;
while (b) {
if (b % 2 == 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
auto split(ll pos) {
auto it = S.lower_bound(odt(pos));
if (it != S.end() && it -> left == pos)
return it;
it--;
if (it -> right < pos)
return S.end();
ll l = it -> left, r = it -> right, v = it -> val;
S.erase(it);
S.insert(odt(l, pos - 1, v));
return S.insert(odt(pos, r, v)).first;
}
void assign(ll l, ll r, ll v) {
auto it_r = split(r + 1), it_l = split(l);
S.erase(it_l, it_r);
S.insert(odt(l, r, v));
}
void add(ll l, ll r, ll v) {
auto it_r = split(r + 1), it_l = split(l);
for (auto it = it_l; it != it_r; it++)
it->val += v;
}
ll rank(ll l, ll r, ll x) {
std::vector< std::pair<ll, ll> > V;
auto it_r = split(r + 1), it_l = split(l);
for (auto it = it_l; it != it_r; it++)
V.push_back(std::make_pair(it -> val, (it -> right) - (it -> left) + 1));
std::sort(V.begin(), V.end());
auto it = V.begin();
while (it != V.end() && it -> second < x)
x -= (it -> second),it++;
return it -> first;
return -1;
}
ll calc(ll l, ll r, ll x, ll y) {
auto it_r = split(r + 1), it_l = split(l);
ll ans = 0;
for (auto it = it_l; it != it_r; ++it)
ans = (ans + qpow(it -> val, x, y) * (it -> right - it -> left + 1) % y) % y;
return ans;
}
inline ll rnd() {
ll ans = seed;
seed = (seed * 7 + 13) % mod;
return ans;
}
int main() {
scanf("%lld%lld%lld%lld", &n, &m, &seed, &vmax);
for (int i = 1; i <= n; i++)
S.insert(odt(i, i, (rnd() % vmax) + 1));
for(int i = 1; i <= m; i++) {
ll op = (rnd() % 4) + 1, l = (rnd() % n) + 1, r = (rnd() % n) + 1, x, y;
if (l > r)
std::swap(l, r);
if (op == 3)
x = (rnd() % (r - l + 1)) + 1;
else
x = (rnd() % vmax) + 1;
if (op == 4)
y = (rnd() % vmax) + 1;//严格按照伪代码要求生成数据
switch (op) {
case 1 : add(l, r, x); break;
case 2 : assign(l, r, x); break;
case 3 : printf("%lld\n", rank(l, r, x)); break;
case 4 : printf("%lld\n", calc(l, r, x, y)); break;
}
}
return 0;
}
题后闲话
写完还要被老妈催去睡觉，烦耶……
过几天就要期考了，祝自己期考顺利ww