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)\) 。