朝乾夕惕，功不唐捐。

内容基本来自 OI-Wiki。

插值是通过已知的、离散的数据点，推算未知的新数据点的方法。

最普通地，可以将原数据点用线段连接，构成分段函数，叫做线性插值；C++ 20 开始，标准库实现了 std::lerp 函数，用于线性插值。

有些时候，为了实现特殊的需求，我们可能需要编写交互库，要求选手链接。

常见的情景有：

• 强制在线：一些题目不强制在线可能会被“乱搞”通过。例如可持久化数据结构有众所周知的离线做法。
• 加速输入输出：一些题目为了要求严格线性可能需要 $10^8$ 以上的输入量，如此大的数据必须在内存生成并交换。
• 限制操作：一些思维题不允许选手直接读取数据，而是要求选手做特定询问获取详细内容；或者可能限制操作次数。
• 人机对抗：另一些思维题要求选手找到最优策略，那么可以要求选手通过接口与交互库对抗。

既然交互库要链接选手的程序，就必须做好防范措施，避免选手使用不当操作 $\textcolor{green}{\text{AC}}$。

珂朵莉树（Chtholly Tree），又名老司机树 ODT（Old Driver Tree）。起源自 CF896C。

实际上，这种想法的本质是基于数据随机的「颜色段均摊」，而不是一种数据结构。

使用 set 实现的珂朵莉树的 assign、add、sum 操作复杂度为 $O(n\log\log n)$.

ODT 的核心思想是将值相同的区间合并为一个结点维护，只要有区间赋值的题目都可以用 ODT 骗分。

ODT 在随机数据上表现良好，但是不保证数据随机时，会被构造数据卡到 T 飞。

通常来说，在使用线段树维护区间操作时，需要使操作在区间上能被快速计算，经典的区间加-区间求和是一个简单的例子。

但是，这里也有一个看似难以维护的反例：

bzoj 3211 花神游历各国

维护一个序列 $A$，初始值为 $A=(a_1,a_2,a_3,\cdots,a_n)$，支持以下操作 $q$ 次：

1. 区间求和
2. 对区间每个数求平方根（向下取整）

$1\le n,q\le 1\times 10^5,0\le a_i\le 10^{12}.$

Useless Algorithms 之一。

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

—— $\textcolor{black}{\text{U}}\textcolor{red}{\text{m_nik}}$