YZOJ P3706 [APIO2018]新家

YZOJ P3706 [APIO2018]新家

时间限制:5000MS      内存限制:1048576KB

难度:\(7.0\)

  • 题目描述

五福街是一条笔直的道路,这条道路可以看成一个数轴,街上每个建筑物的坐标都可以用一个整数来表示。

小明是一位时光旅行者,他知道在这条街上,在过去现在和未来共有 \(n\) 个商店出现。第 \(i\) 个商店可 以使用四个整数 \(x_i , t_i , a_i , b_i\) 描述,它们分别表示:商店的坐标、商店的类型、商店开业的年份、商店关闭的年份。

小明希望通过时光旅行,选择一个合适的时间,住在五福街上的某个地方。他给出了一份他可能选择的列表,上面包括了 \(q\) 个询问,每个询问用二元组 (坐标,时间)表示。第 \(i\) 对二元组用两个整数 \(l_i , y_i\) 描述,分别表示选择的地点 \(l_i\) 和年份 \(y_i\) 。

现在,他想计算出在这些时间和地点居住的生活质量。他定义居住的不方便指数为:在居住的年份,离 居住点最远的商店类型到居住点的距离。类型 \(t\) 的商店到居住点的距离定义为:在指定的年份,类型 \(t\) 的所有营业的商店中,到居住点距离最近的一家到居住点的距离。我们说编号为 \(i\) 的商店在第 \(y\) 年在营业当且仅当 \(a_i \leq y \leq b_i\) 。注意,在某些年份中,可能在五福街上并非所有 \(k\) 种类型的商店都有至少一家在营业。在这种情况下,不方便指数定义为 \(-1\)。

你的任务是帮助小明求出每对(坐标,时间)二元组居住的不方便指数。

  • 输入格式

第一行包含三个整数 \(n,k\) 和 \(q\) ,分别表示商店的数量、商店类型的数量和(坐标,时间)二元组的数量(\(1 \le n, q \le 3 \times 10^5 , 1 \le k \le n\))

接下来 \(n\) 行,每行包含四个整数 \(x_i , t_i , a_i\) 和 \(b_i\) 用于描述一家商店,意义如题面所述 (\(1 \le x_i , a_i , b_i \le 10^8 , 1 \le t_i \le k, a_i \le b_i\))。

接下来 \(q\) 行,每行包含两个整数 \(l_i\) 和 \(y_i\) ,表示一组(坐标,时间)查询 (\(1 \le l_i , y_i \leq 10^8 \))。

  • 输出格式

输出一行,包含 \(q\) 个整数,依次表示对于 \(q\) 组(坐标,时间)询问求出的结果。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

在第一个样例中,有 \(4\) 家商店,共 \(2\) 种类型,还有 \(4\) 个询问。

• 对于第一个询问:小明在第 \(3\) 年住在坐标为 \(5\) 的地方。这一年中,编号为 \(1\) 和 \(2\) 的商店在营业, 到编号为 \(1\) 的商店的距离为 \(2\) ,到编号为 \(2\) 的商店距离为 \(4\) ,所以最大距离为 \(4\)。

• 对于第二个询问:小明在第 \(6\) 年住在坐标为 \(5\) 的地方。这一年中,编号为 \(1\) 和 \(3\) 的商店在营业, 到编号为 \(1\) 的商店的距离为 \(2\) ,到编号为 \(3\) 的商店距离为 \(2\) ,所以最大距离为 \(2\)。

• 对于第三个询问:小明在第 \(9\) 年住在坐标为 \(5\) 的地方。这一年中,编号为 \(1\) 和 \(4\) 的商店在营业, 它们的类型都为 \(1\),没有类型为 \(2\) 的商店在营业,所以答案为 \(-1\)。

• 同样的情况出现在第四个询问中。

 

 

 


 

 

 

其实很简单,就是DataStructure大力维护操作。

首先按照时间离散化,分成三种类型:出现,消失,询问。

对于一个询问 \(x\),可以想到二分答案 \(mid\) 表示 \([x-mid, x+mid]\) 中是否存在所有类型的商店。

由于只要判断是否存在,所以可以记录 \(pre_x\) 表示位于 \(x\) 坐标的商店 往左第一个出现的同种类型的商店(不包括重复)。

假设 \(-\infty\) 和 \(+\infty\) 处有所有类型的商店,那么:

\([l, r]\) 中存在所有类型的商店,其实等价于 \(\min\limits_{x=r+1}^{+\infty}{pre_x} \geq l\) ,因为 \((pre_x, x)\) 中不存在这种类型的商店。

\(pre\) 使用全局线段树维护(动态开点/离散化 均可),由于有删除(修改)操作,所以对每个叶子结点维护一个可删堆(或 multiset)。

还有,由于增加删除商店的时候,会对某个坐标的后继的 \(pre\) 产生影响,所以对每种类型的商店都维护一个 multiset 支持查找前驱后继。

暴力二分线段树判断是 \(O(nlog^2n)\) ,套在一起就可以 \(O(nlogn)\) 。

具体来说就是对于线段树上一段区间 \([l, r]\) :如果 \(pos > mid\) 那么答案区间的右端点肯定在右半边,往右走;否则考虑 \(mid\) 是否能作为答案区间的右端点,若可以即 \(\min\limits_{x=mid+1}^{+\infty} {pre_x} \geq pos-\left(mid-pos\right)\) 那么肯定往左走更优,否则也只能向右走。

这个东西(指 \(\min\limits_{x=mid+1}^{+\infty} {pre_x}\))很明显向左走的时候 \(mid\) 是单调递减的,又由于是在线段树上,所以只需要在往左走的时候维护即可。

最后在线段树上二分出来的 \(ans\) 是答案区间的右端点,要求的答案为 \(mid=ans-pos\) 。

 

 

 

草还有为什么我的 std::multiset__gnu_pbds::tree  还快

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注