A7614. [ABC136F] Enclosed Points
编程题
省选/NOI-
知识点
题目描述
在二维平面上有 $N$ 个点组成的集合 $S$，第 $i$ 个点的坐标为 $(x_i, y_i)$。所有点的 $x$ 坐标和 $y$ 坐标各不相同。
对于 $S$ 的任意非空子集 $T$，定义 $f(T)$ 为：覆盖 $T$ 中所有点且各边与坐标轴平行的最小矩形，包含的 $S$ 中的点的个数。更准确地说：
- 设 $T$ 中点的 $x$ 坐标的最小值和最大值分别为 $a, b$，$y$ 坐标的最小值和最大值分别为 $c, d$，则 $f(T)$ 等于满足 $a \leq x_i \leq b$ 且 $c \leq y_i \leq d$ 的 $1 \leq i \leq N$ 的点的个数。
请计算 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和。答案可能很大，请输出对 $998244353$ 取模的结果。
对于 $S$ 的任意非空子集 $T$，定义 $f(T)$ 为：覆盖 $T$ 中所有点且各边与坐标轴平行的最小矩形，包含的 $S$ 中的点的个数。更准确地说：
- 设 $T$ 中点的 $x$ 坐标的最小值和最大值分别为 $a, b$，$y$ 坐标的最小值和最大值分别为 $c, d$，则 $f(T)$ 等于满足 $a \leq x_i \leq b$ 且 $c \leq y_i \leq d$ 的 $1 \leq i \leq N$ 的点的个数。
请计算 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和。答案可能很大，请输出对 $998244353$ 取模的结果。
输入格式
输入按以下格式从标准输入读入。
> $N$
> $x_1$ $y_1$
> $\vdots$
> $x_N$ $y_N$
> $N$
> $x_1$ $y_1$
> $\vdots$
> $x_N$ $y_N$
输出格式
请输出 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和对 $998244353$ 取模的结果。
输入输出样例
输入 #1
3 -1 3 2 1 3 -2
输出 #1
13
输入 #2
4 1 4 2 1 3 3 4 2
输出 #2
34
输入 #3
10 19 -11 -3 -12 5 3 3 -15 8 -14 -9 -20 10 -9 0 2 -7 17 6 -6
输出 #3
7222
说明/提示
## 限制条件
- $1 \leq N \leq 2 \times 10^5$
- $-10^9 \leq x_i, y_i \leq 10^9$
- $x_i \neq x_j\ (i \neq j)$
- $y_i \neq y_j\ (i \neq j)$
- 输入均为整数
## 样例解释 1
将第 $1, 2, 3$ 个点分别记为 $P_1, P_2, P_3$。$S = \{P_1, P_2, P_3\}$ 的所有非空子集共有 $7$ 个，各自的 $f$ 值如下：
- $f(\{P_1\}) = 1$
- $f(\{P_2\}) = 1$
- $f(\{P_3\}) = 1$
- $f(\{P_1, P_2\}) = 2$
- $f(\{P_2, P_3\}) = 2$
- $f(\{P_3, P_1\}) = 3$
- $f(\{P_1, P_2, P_3\}) = 3$
这些值的和为 $13$。
## 样例解释 3
请注意输出时要对 $998244353$ 取模。
- $1 \leq N \leq 2 \times 10^5$
- $-10^9 \leq x_i, y_i \leq 10^9$
- $x_i \neq x_j\ (i \neq j)$
- $y_i \neq y_j\ (i \neq j)$
- 输入均为整数
## 样例解释 1
将第 $1, 2, 3$ 个点分别记为 $P_1, P_2, P_3$。$S = \{P_1, P_2, P_3\}$ 的所有非空子集共有 $7$ 个，各自的 $f$ 值如下：
- $f(\{P_1\}) = 1$
- $f(\{P_2\}) = 1$
- $f(\{P_3\}) = 1$
- $f(\{P_1, P_2\}) = 2$
- $f(\{P_2, P_3\}) = 2$
- $f(\{P_3, P_1\}) = 3$
- $f(\{P_1, P_2, P_3\}) = 3$
这些值的和为 $13$。
## 样例解释 3
请注意输出时要对 $998244353$ 取模。