E - 计算中位数

分值: $500$ 分

问题描述

给定 $N$ 个整数 $X_1, X_2, \cdots, X_N$，已知 $A_i \leq X_i \leq B_i$。 求 $X_1, X_2, \cdots, X_N$ 的中位数可以取到的不同值的数量。

注意事项

$X_1, X_2, \cdots, X_N$ 的中位数定义如下。将 $X_1, X_2, \cdots, X_N$ 按升序排列得到 $x_1, x_2, \cdots, x_N$。

• 如果 $N$ 是奇数，则中位数为 $x_{(N+1)/2}$；
• 如果 $N$ 是偶数，则中位数为 $(x_{N/2} + x_{N/2+1}) / 2$。

约束

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq B_i \leq 10^9$
• 输入中的所有值都为整数。

输入

输入以以下格式从标准输入给出：

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_N$ $B_N$

输出

输出答案。

2
1 2
2 3

3

• 如果 $X_1 = 1$ 且 $X_2 = 2$，则中位数为 $\frac{3}{2}$；

• 如果 $X_1 = 1$ 且 $X_2 = 3$，则中位数为 $2$；

• 如果 $X_1 = 2$ 且 $X_2 = 2$，则中位数为 $2$；

• 如果 $X_1 = 2$ 且 $X_2 = 3$，则中位数为 $\frac{5}{2}$。

因此，中位数可以取到三个值：$\frac{3}{2}$, $2$ 和 $\frac{5}{2}$。

3
100 100
10 10000
1 1000000000

9991