rprmq2

YLWang · 2021-12-07 15:46:04 · 题解

高维数据结构博大精深。

题意简述

平面上矩形加，查询矩形最大值。操作有特殊形式，无特殊性质。

前置知识

历史最值线段树。

如果会 rmrmq1 再好不过。

吐槽

std 是真快啊。而且完全不看懂 std 是咋写的。

题解

1.O(n \sqrt{n} \log n)

首先暴力 O(n^2 {\rm polylog}\ n) 的做法不加赘述。随便搞搞就好。

我们的思想是对操作序列分块。不妨令块长为 B。

对于每块内的矩形操作，问题可以简化为在一个 O(B)\times O(B) 的有初值的平面上执行子问题。子问题采用暴力。

• 那么如何得到初值？

考虑遍历之前所有操作对当前平面的影响。

我们发现，可以按 rprmq1 的思想去扫描线一维，维护另一维的历史最大值即可。

复杂度 O(\dfrac{m}{B}(B^2\log B + m\log m))。取 B = \sqrt{n} 即可。

2.O(n \sqrt{n \log n})

这个 \log m 看着去不掉了。能不能去个 \log B 呢？

是可以的。具体的，我们发现，在前半部分中，B 组，即平面上每行查询的所有区间都是相同的。

于是稍稍对线段树的形态进行一些扭曲即可保证每个查询被一个区间对应，而非 O(\log) 个。

同时，后半部分的暴力我们直接采用 kdt。建树 O(B^2)，查询 O(\sqrt{B^2})=O(B) 即可。

复杂度 O(\dfrac{m}{B}(B^2 + m\log m))。取 B = \sqrt{n \log n} 即可。

3. 实现方式

……不大会卡常。洛谷的这个题是别想过了，放一份 cf 上题的代码。

Q：为什么时限是 15s 你跑了 20s 给你过了啊？

A：

不知道 std 有没有高明的去 \log 方法。