#P6472. [thoi2012]森林旅店

    ID: 5066 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-K-D Tree按维度中位数划分包围盒剪枝离线预收集坐标二叉堆平方距离比较搜索顺序优化

[thoi2012]森林旅店

题目描述

树林中的每棵树用一个整数坐标表示,同一坐标至多有一个白蚁穴。初始有 NN 个白蚁穴。接下来处理 QQ 次操作,每次加入一个白蚁穴,或者查询某点到当前最近的 PP 个白蚁穴各有多远。

位置 (x1,y1)(x_1,y_1) 与 (x2,y2)(x_2,y_2) 的距离定义为

(∣x1−x2∣K+∣y1−y2∣K)1/K.\left(|x_1-x_2|^K+|y_1-y_2|^K\right)^{1/K}.

输入格式

第一行四个整数 N,Q,K,PN,Q,K,P。接下来 NN 行,每行两个整数,表示初始白蚁穴的坐标。

再接下来 QQ 行,每行一个字符及两个整数 x,yx,y。

  • A x y 表示在 (x,y)(x,y) 加入一个白蚁穴。
  • Q x y 表示查询从 (x,y)(x,y) 到当前最近的 PP 个白蚁穴的距离。

查询时至少有 PP 个白蚁穴。

输出格式

每次查询输出一行 PP 个实数,按距离从小到大排列,以空格分隔,保留小数点后四位。

样例

1 3 1 1
0 0
Q 0 2
A 0 3
Q 0 2
2.0000
1.0000

数据范围

原题数据分为以下十组,每组五个测试点。表中 N,QN,Q 为上界,K,PK,P 为该组参数。每组有 40%40\% 的数据没有插入操作,所有数据中查询次数不超过 50005000。

组别 NN QQ KK PP
1 5000 2000 1 1
2 20000 10000 3
3 100000 5000
4 20000
5 20000 2000 2 1
6 20000 3
7 100000 5000
8 20000
9
10

原 PDF 说明白蚁穴坐标由随机点分别经两个单调函数变换,标注坐标在 [0,107][0,10^7]。本站现有评测中的初始、插入和查询坐标均为整数,实际范围为 [−5729,10031468][-5729,10031468],实现应支持负坐标和超过 10710^7 的坐标。

原 PDF 题面第 1 页 · 原 PDF 题面第 2 页