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