超脑少年哲哲帝题
题目大意.
现在有一个
的网格。每个格子有一个权值,权值互不相同。
阶领主拥有整个网格。他将在他的领地中选择他所处的位置:如果 ,那么他将选择站在领地中权值最小的格子上;否则他将选择站在领地中权值最大的格子上。然后他会将他的领地分为 块,每个非空的块都会分封给一个 阶领主并重复这个过程。注意与他同行或同列的格子会被直接弃置。 问:每个格子上的领主的封君是谁。
芬兰国旗(幻视)
。 时限 700ms,空限 80MB。
根据空间限制,基本上所有高维数据结构都不能使用。而时间限制把唯一的漏网之鱼 KDT 也干掉了。
考虑分块。
对每个元素记录:
除了
考虑"重链剖分"。考虑整个矩形的中心点,我们处理出它到四个角的矩形最大 / 最小值。如果一个子矩形包含这个中心点,那么我们就可以直接查阅。而不包含这个中心点的矩形必定是"轻儿子",大小不超过原矩形的一半。
如图,不断这样分割下去。实际上就是在重链上走到底;即我们可以在根矩形的大小的时间内处理掉一整条重链。
时间复杂度
大胆猜想 zzd 没卡暴力,然后怒敲一发直接过了!!!