题解：AT_cf17_final_i Full Tournament

WaterM · 2026-11-11 11:59:54 · 题解

模拟赛因为被 2 创了所以没有充足时间看这题。后来绕了若干时间就会了。

考虑你对于一个确定的 a 序列怎么还原回去。

你注意到你执行以下过程：设 f(l, r) 表示还原 [l, r] 的序列。

然后你执行 f(l, mid), f(mid + 1, r)，然后你再依次取 a_l, a_{mid+1},a_{l+1},a_{mid+2},\dots 拼起来。

那么你的限制就是形如这么 merge 的时候，要求 a_{mid+i}>a_{l+i-1}。

注意构造过程并不依赖 a，你先按照这个二元关系建出来 DAG，那么你就要将 a 补全，使得满足二元关系。

这个东西后来知道是有原题的。

考虑你正着和反着扫一遍，那么你每一个没填的 a_i 都有一个上下界。

你再拓扑排序一遍，然后每次优先加入上界小的，用堆维护。然后你维护一个值表示当前该填什么数了，每次加入的时候当下界小于等于这个值的时候才加入，大了就等到值挪动到那里才解锁。

然后无解就是没数可填了。

时间复杂度 O(2^nn)。