1class Solution {
2    /**
3     * For each query [l, r], we consider all integers in the range [l, r].
4     * Each integer x requires a certain number of operations to reduce it to 0,
5     * where each operation divides the number by 4 (the operation count equals
6     * floor(log4(x)) + 1, i.e., the "level" of x in powers of 4).
7     *
8     * Since one operation can act on two numbers at once, the minimum number of
9     * operations for a single query is max(ceil(totalSteps / 2), maxSteps),
10     * where totalSteps is the sum of steps over all numbers in [l, r], and
11     * maxSteps is the largest step count among numbers in [l, r].
12     */
13    public long minOperations(int[][] queries) {
14        long answer = 0;
15        for (int[] query : queries) {
16            int left = query[0], right = query[1];
17
18            // Total number of single-element reduction steps for the range [left, right].
19            long totalSteps = countSteps(right) - countSteps(left - 1);
20
21            // Maximum step count in the range, which equals the step count of the
22            // single largest number 'right' (since steps are non-decreasing with value).
23            long maxSteps = countSteps(right) - countSteps(right - 1);
24
25            // Each operation handles two numbers, so we need at least ceil(totalSteps / 2)
26            // operations; but we also need at least maxSteps operations to fully reduce
27            // the largest number.
28            answer += Math.max((totalSteps + 1) / 2, maxSteps);
29        }
30        return answer;
31    }
32
33    /**
34     * Computes the prefix sum of step counts for all integers in [1, x].
35     *
36     * A number n belongs to "level" i (1-indexed) if 4^(i-1) <= n <= 4^i - 1,
37     * meaning it takes i operations to reduce n to 0 by repeated division by 4.
38     *
39     * For each level i, this method counts how many numbers in [1, x] fall into
40     * that level and accumulates (count * i) into the result.
41     *
42     * @param x the upper bound of the range [1, x]
43     * @return the sum of step counts for all integers from 1 to x
44     */
45    private long countSteps(long x) {
46        long result = 0;
47        long power = 1; // power = 4^(i-1), the lower bound of the current level
48        int level = 1;  // current level index (number of operations for this level)
49
50        while (power <= x) {
51            // Upper bound of the current level is (4^i - 1) = power * 4 - 1,
52            // clamped by x. Lower bound is 'power'.
53            long count = Math.min(power * 4 - 1, x) - power + 1;
54            result += count * level;
55
56            level++;
57            power *= 4;
58        }
59        return result;
60    }
61}
62

1class Solution {
2public:
3    long long minOperations(vector<vector<int>>& queries) {
4        // f(x) returns the total number of divide-by-4 operations required
5        // to reduce every integer in the range [1, x] down to 0.
6        // A value v needs (floor(log4(v)) + 1) operations.
7        // All values in [4^(i-1), 4^i - 1] share the same cost i.
8        auto f = [&](long long x) -> long long {
9            long long total = 0;  // accumulated operation count
10            long long power = 1;  // current block start, equals 4^(i-1)
11            int cost = 1;         // number of operations for values in this block
12            while (power <= x) {
13                // Right boundary of the current block, clamped to x.
14                long long blockEnd = min(power * 4 - 1, x);
15                // Count of integers in this block within [1, x].
16                long long count = blockEnd - power + 1;
17                total += count * cost;
18                cost++;
19                power *= 4;  // move to the next block: 4^i
20            }
21            return total;
22        };
23
24        long long ans = 0;
25        for (auto& query : queries) {
26            int left = query[0], right = query[1];
27
28            // Total operations needed for the whole range [left, right].
29            long long sum = f(right) - f(left - 1);
30
31            // Operations needed by the single largest element 'right'.
32            long long maxCost = f(right) - f(right - 1);
33
34            // Each operation processes two numbers, so we need at least
35            // ceil(sum / 2) operations; but also at least maxCost since one
36            // element cannot be sped up by pairing.
37            ans += max((sum + 1) / 2, maxCost);
38        }
39        return ans;
40    }
41};
42

1/**
2 * Computes the total number of operations required to reduce every integer
3 * in the range [1, x] down to zero, where each operation divides a value by 4
4 * (using floor division). A number n located in the bucket [4^(i-1), 4^i - 1]
5 * needs exactly i operations to reach zero.
6 *
7 * @param x - The upper bound of the range [1, x].
8 * @returns The total operation count for all integers in [1, x].
9 */
10const f = (x: number): number => {
11    let result = 0;
12    let power = 1; // Represents 4^(i-1), the lower bound of the current bucket.
13    let steps = 1; // Number of operations needed for numbers in the current bucket.
14
15    while (power <= x) {
16        // Count how many integers fall within the current bucket [power, 4*power - 1],
17        // capped by x so we never count beyond the requested range.
18        const count = Math.min(power * 4 - 1, x) - power + 1;
19        result += count * steps;
20        steps++;
21        power *= 4; // Move to the next bucket.
22    }
23
24    return result;
25};
26
27/**
28 * For each query [l, r], determines the minimum number of operations to reduce
29 * all integers in [l, r] to zero. Each operation can divide up to two numbers
30 * by 4 simultaneously, so the answer is bounded below by:
31 *   - ceil(totalOperations / 2): because two numbers are handled per operation.
32 *   - maxOperations: the hardest single number still needs its full step count.
33 *
34 * @param queries - A list of [l, r] ranges.
35 * @returns The accumulated minimum operations across all queries.
36 */
37function minOperations(queries: number[][]): number {
38    let ans = 0;
39
40    for (const [l, r] of queries) {
41        // Total operations needed for all integers in [l, r].
42        const sum = f(r) - f(l - 1);
43        // Operations needed for the single hardest number, which is r.
44        const max = f(r) - f(r - 1);
45        // Pair up operations (two per step) but never go below the hardest element.
46        ans += Math.max(Math.ceil(sum / 2), max);
47    }
48
49    return ans;
50}
51