問題
$n$ 個の区間 $[A _ i, B _ i]$ が与えられる。各 $X _ i$ が $A _ i \leq X _i \leq B _ i$ を動くとき、$X _ 1, \ldots , X _ n$ の中央値として取りうる値は何個あるか。（$n \leq 2 \times 10 ^ 5$）
解説
$A$ の中央値を $a$、$B$ の中央値を $b$ とする。
以下の手順で $X$ を変化させていくことで、$n$ が奇数の場合は $a,a+1,\ldots,b$、$n$ が偶数の場合は $a,a+0.5,a+1,\ldots,b$ を $X$ の中央値がとるようにできる。
最初、$X = A$ とする。$X _ 1$ を $1$ ずつ増やしていき、$X _ 1 = B _ 1$ になったら $X _ 2$ を $1$ ずつ増やし、$X _ 2 = B _ 2$ になったら $X _ 3$ を $1$ ずつ増やし、... として最終的に $X=B$ にする。
ある $X _ i$を $1$ 増やしたとき、$n$ が奇数の場合は増やした $X _ i$ がそのまま中央値になったとき $X$ の中央値は $1$ 増え、そうでないときは $X$ の中央値は変化しないので、$X$ の中央値は $a$ から $b$ まで $1$ 刻みですべての値をとる。また、$n$ が偶数の場合は中央値はある $2$ つの $X _ i,X _ j$ の平均なので増やしたのがこのどちらかのとき $X$ の中央値は $0.5$ 増え、そうでないなら $X$ の中央値は変化しないので、$a$ から $b$ まで $0.5$ 刻みですべての値をとる。
実装
n = int(input()) AB = [tuple(map(int, input().split())) for i in range(n)] A = sorted([a for a, b in AB]) B = sorted([b for a, b in AB]) if n % 2 == 0: print((B[n // 2 - 1] + B[n // 2]) - (A[n // 2 - 1] + A[n // 2]) + 1) else: print(B[n // 2] - A[n // 2] + 1)
