← 返回题目列表

AtCoder · abc136_f

F. 封闭点

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一套 S of N 点位于二维平面中。的坐标 i第一点是 (x_i, y_i)。的 N 点有明显的 x- 坐标和不同 y- 坐标。

对于非空子集 T of S,让 f(T) 是最小矩形中包含的点数,其边平行于坐标轴,包含 T。更正式地,我们定义 f(T) 如下:

  • f(T) := (整数个数 i (1 \leq i \leq N) 这样 a \leq x_i \leq b 和 c \leq y_i \leq d,其中 a, b, c,和 d 是最小值 x- 坐标,最大值 x- 坐标,最小值 y- 坐标,最大 y- 中的点的坐标 T)

求总和 f(T) 所有非空子集 T of S。由于它可能很大,因此打印模数之和 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)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
:
x_N y_N

输出

打印总和 f(T) 所有非空子集 T of S,模数 998244353.


示例输入 1

3
-1 3
2 1
3 -2

示例输出 1

13

设第一点、第二点和第三点为 分别为 P_1, P_2,和 P_3。 S = \{P_1, P_2, P_3\} 有七个非空子集,并且 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.


示例输入 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

请务必打印模数总和 998244353.