P7122 Chino and Segment Trees

Chino has just learned a data structure called the segment tree. However, she ran into a problem when writing a segment tree: she does not know how much space to allocate. She only knows that the number of leaf nodes $n$ is a positive integer within the range $[a,b]$. Chino defines $f(n)$ as the maximum array index used by a segment tree with $n$ leaf nodes. She believes that if she knows $$\sum_{n=a}^{b}f(n)$$ then she can figure out how much space she needs. So she asks you, the clever one, to help her. Specifically, the pseudocode for building the segment tree is as follows: $\begin{aligned} &\underline{\kern{300pt}}\\ &\mathbf{Function:}\ \text{Build a Segment Tree.}\\[-10pt] &\underline{\kern{300pt}}\\[-5pt] &\begin{array}{r|l} 1&\ \mathbf{function}\ \text{BuildSegmentTree}(x,l,r):\\ 2&\qquad \mathbf{if}\ (l \ne r)\ \mathbf{then}:\\ 3&\qquad\qquad m \gets \left\lfloor (l+r)/2 \right\rfloor\\ 4&\qquad\qquad \text{BuildSegmentTree}(2x,l,m)\\ 5&\qquad\qquad \text{BuildSegmentTree}(2x+1,m+1,r)\\ 6&\qquad \mathbf{end\ if}\\ 7&\ \mathbf{end\ function}\\ \end{array}\\[-13pt] &\underline{\kern{300pt}} \end{aligned}$ The maximum array index used by the segment tree is the maximum value of the parameter $x$ among all calls to $\def\t#1{\text{#1}}\t{BuildSegmentTree}$ after executing $\def\t#1{\text{#1}}\t{BuildSegmentTree}\left(1,1,n\right)$.

The input has two lines. The first line contains a positive integer $a$; the second line contains a positive integer $b$. Their meanings are as described in the statement.

Output one line containing one positive integer, which is your answer.

### Sample Explanation #1 For segment trees with $1\sim 10$ leaf nodes, the maximum indices are $1,3,5,7,9,13,13,15,17,25$, respectively. Summing them gives $108$. ### Test Point Constraints **This problem uses bundled testdata.** For all data, $1\le a\le b\le10^{10^6}$. The specific limits for each subtask are shown in the table below: | Subtask ID | Score | $b\le$ | $a=b$ | |:-:|:-:|:-:|:-:| | 1 | 10 | $10^{10^0}$ | $\times$ | | 2 | 10 | $10^{10^1}$ | $\times$ | | 3 | 10 | $10^{10^2}$ | $\times$ | | 4 | 10 | $10^{10^3}$ | $\surd$ | | 5 | 10 | $10^{10^3}$ | $\times$ | | 6 | 10 | $10^{10^4}$ | $\surd$ | | 7 | 10 | $10^{10^4}$ | $\times$ | | 8 | 10 | $10^{10^5}$ | $\surd$ | | 9 | 10 | $10^{10^5}$ | $\times$ | | 10 | 10 | $10^{10^6}$ | $\times$ | Translated by ChatGPT 5