高阶扩展：随机输入契约与有序区间树

建议先完成课前零食：把相同的一段装进一个盒子。它从段卡、split 边界和一个故意构造的坏例子出发，避免把 ODT 误当成万能的均摊对数结构。

本节目标

理解有序区间树（Ordered Disjoint Tree, ODT/Chtholly Tree）的真实适用条件：它维护等值段，依靠随机数据中的区间赋值压缩段数；能说明其期望性能来源，也能构造对抗数据证明它不是通用平衡树模板。

前置知识与课前自测

前置：std::set、迭代器失效、快速幂、随机生成器。

把数组压成极大等值段后，区间赋值会让段数怎样变化？
区间加法会不会合并大量段？
若操作由题面固定伪随机生成，平均情况假设是否属于输入契约的一部分？

答案

1. 删除内部所有段并至多新建一个段，通常显著减少段数。 2. 不会；它只改变覆盖段的值。 3. 是，但必须严格复现生成器；对任意手工输入不能沿用期望复杂度结论。

问题动机

四类操作无法由常规固定摘要自然统一；题面把操作全部随机生成，是在邀请我们把“等值段数量的期望受控”纳入复杂度分析，而不是寻找一个虚构的最坏情况对数模板。

精选例题：Willem, Chtholly and Seniorious

来源与题意

VJudge：CodeForces-896C
原题：Codeforces 896C
难度：2600；考点：等值段集合、split、区间赋值摊还、输入生成契约

$n,m\le10^5$。数组和全部操作由给定线性同余伪随机生成器产生；支持区间加、区间赋值、区间第 $k$ 小、区间幂和模任意 $y$。

Hint 1

四类操作很难由一个固定维度的线段树摘要同时支持；尤其第 k 小与任意指数幂和。

Hint 2

维护互不相交且覆盖数组的等值段 `(l,r,value)`，按 l 排序。

Hint 3

`split(pos)` 把包含 pos 的段切成 `[l,pos-1]` 与 `[pos,r]`，并返回后者迭代器。

Hint 4

对 `[l,r]` 先 split(l)、split(r+1)，之后覆盖段在 set 中形成一个连续迭代器区间。

从朴素到数据结构

逐点操作最坏 $O(nm)$。线段树能处理区间加/赋值，但“第 $k$ 小”和“任意临时指数、临时模数的幂和”没有小而稳定的合并摘要。题面却保证所有数据与操作按固定随机序列生成，且四种操作均匀出现；频繁的随机区间赋值会删除大量旧断点。

ODT 维护当前等值段。统一切出 [l,r] 后：

加法：遍历覆盖段并修改 value；
赋值：擦除覆盖段，插入单段 [l,r,x]；
第 $k$ 小：收集 (value,length)，按值排序后扣长度；
幂和：对每段加 length * value^x mod y。

单次耗时与被访问段数成正比（第 $k$ 小再乘排序对数）。随机赋值持续把长区间压成一个段，使期望总访问量可接受。

正确性证明

不变量是 set 中各段按左端点严格递增、互不重叠、并集为 $[1,n]$，且段内数组值相同。split 只把一段拆成两个同值段，不改变数组；之后 [split(l),split(r+1)) 恰覆盖查询区间。

加法逐段修改与逐元素加等价；赋值删除恰好覆盖范围并插入统一值；查询中每段长度等于该值在区间贡献的元素数。因此四种操作都保持不变量并返回精确答案。

复杂度边界

确定性最坏复杂度仍可达 $O(nm)$：交替制造大量单点不同值，再查询整段即可扫描 $\Theta(n)$ 段。这里通过的依据是题目指定的伪随机生成过程与大量随机区间赋值带来的期望段数控制，不可写成“ODT 保证均摊 $O(\log n)$”。

实现指南、核心伪代码与附件

split(pos):
    find interval [l,r,v] containing pos
    if l == pos: return it
    replace it by [l,pos-1,v] and [pos,r,v]
    return iterator of [pos,r,v]

operate(l,r):
    end = split(r+1)
    begin = split(l)
    # [begin,end) is exactly the affected interval list

完整 GNU C++17 实现

扩展与联系

ODT 与平衡树的联系只在于用有序集合维护断点；它不维护树形聚合信息。分块也能利用随机赋值重构块，但性能模型与实现边界不同。

实现细节、复盘与变式

节点按 l 比较；r,value 必须可通过 const 迭代器修改，常用 mutable。
赋值时先取得 end=split(r+1)，再取得 begin=split(l)，随后整体 erase(begin,end)。
必须逐字复现 rnd() 的调用次数；第 3 类和其他操作生成 x 的取模不同，第 4 类还多生成 y。
幂和先把底数模 y；本题 y\le10^9，64 位乘法足够。
若输入改为用户显式给出的对抗操作，本节实现不再有性能保证，应换带有序统计/值域结构的更强方案。

总结与自检

写出一个让段数长期保持 $\Theta(n)$ 的操作序列；说明 split 为何不改变语义；解释这题的随机性为何属于复杂度契约。

课后训练建议

用小数组逐点模拟对拍四类操作，并额外记录每步段数观察赋值的压缩效果。卡在接口实现时先单测 split(1)、split(n+1) 与连续赋值。

04-高阶扩展-随机输入契约与ODT.md 5.7 KB Permalink History Raw