406717: GYM102503 N Holy Smokes

A row of $$$10^9$$$ cigarettes are on the ground. They have never been touched by an angel before. Today the lives of those cigarettes are going to change. We index these $$$10^9$$$ cigarettes from $$$1$$$ to $$$10^9$$$.

$$$10^9$$$ angels walk through the ground one-by-one. The first angel skips the first cigarette, touches the second, skips the third, touches the fourth and so on. After the first angel finishes, the second angel arrives. The second angel skips the first two cigarettes, touches the next two cigarettes and so on. The third angel arrives when the second angel finishes and so on. For $$$i = 1, \ldots, 10^9$$$, the $$$i$$$th angel skips the first $$$2^{i-1}$$$ cigarettes, touches the next $$$2^{i-1}$$$ cigarettes, skips the next $$$2^{i-1}$$$ cigarettes, and so on. Once the $$$i$$$th angel has touched or has skipped the last cigarette, he then leaves. After the last angel leaves, no other angel comes and the cigarettes are never touched by any angel again.

Between two cigarettes on the ground, the holier cigarette between them is the one which has been touched more times. If the two cigarettes we are comparing have been touched the same number of times, then the holier one between the two of them is the one which has been touched more recently.

Let $$$L$$$ and $$$R$$$ be two integers, with $$$1 \le L \leq R \leq 10^9$$$. We can rank the set of cigarettes with indices $$$L, L+1, \ldots, R$$$ according to holiness. We define the positive integer $$$r_k$$$ to be index of the $$$k$$$th holiest cigarette in this set. In other words, cigarette $$$r_k$$$ is the $$$k$$$th holiest in the set. Given two integers $$$a$$$ and $$$b$$$ with $$$a \leq b$$$, find the sum of $$$r_a + r_{a+1} + \ldots + r_b$$$.

The first line of input contains $$$T$$$, the number of test cases.

Each test case consists of one line containing four space-separated integers $$$L$$$, $$$R$$$, $$$a$$$, $$$b$$$, respectively.

For each test case, output one line containing the answer to that test case.

$$$1 \le T \le 5 \times 10^4$$$

$$$1 \le L \le R \leq 10^9$$$

$$$1 \leq a \leq b \leq R-L+1$$$

Subtask 1 (10 points):

$$$R \le 100$$$

Subtask 2 (15 points):

$$$R \le 2\times 10^5$$$

$$$L$$$ will be the same across all test cases.

$$$R$$$ will be the same across all test cases.

Subtask 3 (30 points):

$$$L$$$ and $$$R$$$ are powers of 2.

$$$a=b$$$

Subtask 4 (25 points):

$$$a=b$$$

Subtask 5 (20 points):

No additional constraints.

1
1 1 1 1

1

3
2 11 6 8
2 11 1 1
2 17 12 14

18
8
31

We will examine the second sample test case.

For the first query, we are concerned with the cigarettes indexed 2 to 11. Then, if we were to sort only these cigarettes according to their holiness, we must find the sum of the 6th holiest, 7th holiest, and 8th holiest cigarettes. You can verify that $$$r_6 = 4$$$, $$$r_7 = 9$$$, and $$$r_8=5$$$. We see that cigarette 4 is holier than cigarette 9, since cigarette 4 was touched by two angels while cigarette 9 was only touched by one angel. Meanwhile, cigarette 9 and cigarette 5 were both only touched by one angel. However, we can show that cigarette 9 was touched by the 4th angel, while cigarette 9 was touched by the 3rd angel, and so cigarette 9 must be the holier one since it was touched more recently. Thus, $$$r_6+r_7+r_8=4+9+5=18$$$.

For the second query, we can verify that no cigarette in the set was touched more than 3 times, and the only cigarette to be touched exactly 3 times is cigarette 8. Thus, the holiest cigarette in the set is equal to 8, and $$$r_1=8$$$.

For the third query, we consider a different set of cigarettes, and we can verify that $$$r_{12} = 17$$$, $$$r_{13} = 9$$$, and $$$r_{14}=5$$$, so $$$r_{12}+r_{13}+r_{14}=17+9+5=31$$$. Notice that since the set of cigarettes is different, the ranks of cigarette 9 and cigarette 5 are different from what they were in the first query.