Divide Interval

题目描述

对于非负整数 $l$ 和 $r$ (l < r)，令 $S(l, r)$ 表示按顺序排列从 $l$ 到 $r-1$ 的整数形成的序列 $(l, l+1, \ldots, r-2, r-1)$。此外，当且仅当一个序列可以用非负整数 $i$ 和 $j$ 表示为 $S(2^i j, 2^i (j+1))$ 时，该序列称为良序列。 给定非负整数 $L$ 和 $R$ (L < R)。将序列 $S(L, R)$ 划分为尽可能少数量的良序列，并输出该序列的数量和划分。更正式地，找到最小的正整数 $M$，使得存在一列非负整数对 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ 满足下列条件，并输出这样的 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$。

$L = l_1 < r_1 = l_2 < r_2 = \cdots = l_M < r_M = R$ $S(l_1, r_1), S(l_2, r_2), \ldots, S(l_M, r_M)$ 都是良序列。

可以证明使 $M$ 最小的划分是唯一的。

输入格式

输入由标准输入按以下格式给出： $L$ $R$

输出格式

按以下格式输出答案： $M$ $l_1$ $r_1$ $\vdots$ $l_M$ $r_M$

注意对 $(l_1, r_1), \dots, (l_M, r_M)$ 的输出应为 升序。

3 19

5
3 4
4 8
8 16
16 18
18 19

0 1024

1
0 1024

3940649673945088 11549545024454656

8
3940649673945088 3940649673949184
3940649673949184 4503599627370496
4503599627370496 9007199254740992
9007199254740992 11258999068426240
11258999068426240 11540474045136896
11540474045136896 11549270138159104
11549270138159104 11549545016066048
11549545016066048 11549545024454656

提示

0 \leq L < R \leq 2^{60} 所有输入值均为整数。$S(3,19)=(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)$ 可以被划分为以下五个良序列，这是可能的最小值：

$S(3,4)=S(2^0\cdot 3,2^0\cdot4)=(3)$ $S(4,8)=S(2^2\cdot 1,2^2\cdot 2)=(4,5,6,7)$ $S(8,16)=S(2^3\cdot 1,2^3\cdot 2)=(8,9,10,11,12,13,14,15)$ $S(16,18)=S(2^1\cdot 8,2^1\cdot 9)=(16,17)$ $S(18,19)=S(2^0\cdot 18,2^0\cdot 19)=(18)$

标签: AtCoder|abc349D

来源

AtCoder|abc349D