YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

时间限制:2000MS      内存限制:262144KB

出题人:zzx      难度:\(6.0\)

  • 题目描述

\(k\) 维空间内有两个点集 \(A=\{X_1,X_2,\ldots,X_m\}\),\(B=\{Y_1,Y_2,\ldots,Y_n\}\),每个点的坐标是一个 \(k\) 元组 \((x_1,x_2,\ldots,x_k)\)。我们称点 \(X(x_1,x_2,\ldots,x_k)\) 控制点 \(Y(y_1,y_2,\ldots,y_k)\) 当且仅当 \(\forall 1\le i\le k,x_i>y_i\),记为 \(X>Y\)。数点问题是要求计算点 \(X_i\) 能控制 \(B\) 中的点数 \(c_i\),即 \(c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|\)。

  • 编程任务

对于给定的点集 \(A\) 和 \(B\),求出对于所有 \(1\le i\le m\) 的 \(c_i\) 的值。

  • 输入格式

第一行有三个正整数\(m\)、\(n\) 和 \(k\),分别表示集合 \(A\) 和 \(B\) 的基数及维数。接下来的 \(m+n\) 行依次给出点 \(X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n\),每个点的坐标用一行 \(k\) 个整数 \(x_1 , x_2 ,\ldots, x_k\) 描述,所有坐标在 \(int\) 范围内。

  • 输出格式

将计算出的 \(c_1 ,c_2 ,\ldots,c_m\) 依次输出到文件中,每个 \(c_i\) 输出 \(1\) 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于数据点 \(1\),\(n,m\le 200,000\),\(k=1\)

对于数据点 \(2\)、\(3\)、\(4\),\(n,m\le 150,000\),\(k=2\)

对于数据点 \(5\)、\(6\)、\(7\),\(n,m\le 100,000\),\(k=3\)

对于数据点 \(8\)、\(9\)、\(10\),\(n,m\le 20,000\),\(k\le 10\)

 

 

 


 

 

 

恶心的四合一好题?

题意就是要求 \(k\) 维偏序的个数。

对于 \(k=1\) 的点,直接 std::sort()std::upper_bound()

对于 \(k=2\) 的点,就是经典的二维偏序,树状数组解决。

对于 \(k=3\) 的点,就是经典的三维偏序,CDQ分治解决。

于是就只能考虑其他算法。

发现 \(n\) 变小了,所以可以考虑平方级别的算法。

暴力枚举所有的维度,按该维度排序,这样每个询问点所能控制的点就可以用一个长度为 \(n\) 的二进制数表示,最后对于每个询问点把它在每个维度下能控制的点求交集,答案就是二进制数上 \(1\) 的个数。

注意到 \(n^2k \approx 4 \times 10^9\) 无法通过本题。

于是,因为是二进制,所以使用 std::bitset 优化。

复杂度 \(O(\frac{n^2k}{\omega} \approx 10^8)\) 。

 

 

 

 

发表评论

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