AT_abc169_e [ABC169E] Count Median

题目描述

有 $N$ 个整数 $X_1, X_2, X_3,\cdots,X_N$，满足 $A_i \le X_i \le B_i$。

求 $X_1，X_2,\cdots,X_N$ 的中位数可能的不同值的数量。

输入格式

输入以以下格式从标准输入提供：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
:
$A_N$ $B_N$

输出格式

一行一个整数，代表可能的不同中位数取值。

Translated by

输入输出样例 #1

输入 #1

2
1 2
2 3

输出 #1

3

输入输出样例 #2

输入 #2

3
100 100
10 10000
1 1000000000

输出 #2

9991

说明/提示

样例解释#1

• 如果 $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}$

提示：

$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 \le N \le 2 \times 10^5$
• $1 \le A_i \le B_i \le 10^9$
• 所有的值均为整数