超脑少年哲哲帝题

题目大意.

现在有一个 $n\times m$$n\times m$ 的网格。每个格子有一个权值，权值互不相同。

$0$$0$ 阶领主拥有整个网格。他将在他的领地中选择他所处的位置：如果 $a_0=0$$a_0=0$，那么他将选择站在领地中权值最小的格子上；否则他将选择站在领地中权值最大的格子上。然后他会将他的领地分为 $4$$4$ 块，每个非空的块都会分封给一个 $1$$1$ 阶领主并重复这个过程。注意与他同行或同列的格子会被直接弃置。

问：每个格子上的领主的封君是谁。

芬兰国旗（幻视）

$n\times m\le 4\times {10}^6$$n\times m\le 4\times10^6$。

时限 700ms，空限 80MB。

根据空间限制，基本上所有高维数据结构都不能使用。而时间限制把唯一的漏网之鱼 KDT 也干掉了。

算法 1

考虑分块。

对每个元素记录：

• 其下方 $B$$B$ 个元素的最大 / 最小值；
• 其右方 $B$$B$ 个元素的最大 / 最小值。

除了 $R,C<B$$R,C<B$ 的极端情况，查询复杂度都是 $RC/B$$RC/B$。但是又会发现一个元素出现于"极端情况"不会超过 $B$$B$ 次，因此时间复杂度为 $O(nmB+nm{\displaystyle \frac{min(n,m)}{B}})$$O(nmB+nm\dfrac{\min(n,m)}{B})$。当 $B=(nm{)}^{0.25}$$B=(nm)^{0.25}$ 时就得到了一个 $O((nm{)}^{1.25})$$O((nm)^{1.25})$ 的做法。如果你是卡常大师就能通过此题。

算法 2

考虑"重链剖分"。考虑整个矩形的中心点，我们处理出它到四个角的矩形最大 / 最小值。如果一个子矩形包含这个中心点，那么我们就可以直接查阅。而不包含这个中心点的矩形必定是"轻儿子"，大小不超过原矩形的一半。

如图，不断这样分割下去。实际上就是在重链上走到底；即我们可以在根矩形的大小的时间内处理掉一整条重链。

时间复杂度 $O(nm\log \left(nm\right))$$O(nm\log(nm))$。

算法 3

大胆猜想 zzd 没卡暴力，然后怒敲一发直接过了！！！