2023.12.22~ 做题记录

1. ICPC2022 Xi'an R A Bridge

感觉很妙啊，应该不止蓝吧？

首先一个转化是每次建桥操作就相当于交换两条链的后半部分，可以看看扶苏那篇题解的图。

我们将每个点表示为形如 \((x, y)\) 的二元组表示它初始在第 \(x\) 行第 \(y\) 列，按 \(y\) 为键值排序，那么一次询问就是查询一条链的最大值。

这些操作可以用 FHQ Treap 完成，就是每次修改 \((a, b)\) 就把两棵 Treap 分别按 \(\le b\) split 成四棵，交换后再 merge。查询直接暴力跳右儿子就行。

但是显然不能存 \(nm\) 个点。考虑我维护连续段而不是维护一个个单点，每个连续段形如 \((x, l, r)\) 表示初始在第 \(x\) 行第 \(l\) 列到第 \(r\) 列的点，意义是它们在同一条链上并且连边 \(l \to l + 1 \to \cdots \to r\)。

那么每次修改操作会多产生 \(4\) 个段，所以段的个数就是 \(O(n + q)\) 的，可以接受。

实现时比较繁琐，每一行要额外开个 set 维护原来在这一行的段方便对于每次修改找到 \(b\) 所在的段，还要开个 map 维护每个三元组 \((x, l, r)\) 对应到 Treap 上的哪个点。为了找对应结点的根还要维护每个点的父亲。

总时间复杂度是 \(O((n + q) \log n)\)。