Who I am
朝乾夕惕,功不唐捐。
朝乾夕惕,功不唐捐。
有些时候,为了实现特殊的需求,我们可能需要编写交互库,要求选手链接。
常见的情景有:
既然交互库要链接选手的程序,就必须做好防范措施,避免选手使用不当操作 $\textcolor{green}{\text{AC}}$。
珂朵莉树(Chtholly Tree),又名老司机树 ODT(Old Driver Tree)。起源自 CF896C。
实际上,这种想法的本质是基于数据随机的「颜色段均摊」,而不是一种数据结构。
使用 set
实现的珂朵莉树的 assign
、add
、sum
操作复杂度为 $O(n\log\log n)$.
ODT 的核心思想是将值相同的区间合并为一个结点维护,只要有区间赋值的题目都可以用 ODT 骗分。
ODT 在随机数据上表现良好,但是不保证数据随机时,会被构造数据卡到 T 飞。
通常来说,在使用线段树维护区间操作时,需要使操作在区间上能被快速计算,经典的区间加-区间求和是一个简单的例子。
但是,这里也有一个看似难以维护的反例:
维护一个序列 $A$,初始值为 $A=(a_1,a_2,a_3,\cdots,a_n)$,支持以下操作 $q$ 次:
- 区间求和
- 对区间每个数求平方根(向下取整)
$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}}$
本文所有代码默认 #include <iostream>
且 using namespace std;
帮 N 老师搞完 Fast IO 页面后有感而发,希望系统地写一下文件读入输出优化。