In a neural network, there are n layers, each with computational time represented by the array computationalTime. Developers are provided with an operation where they can select all layers with computation time c, an even integer. They then adjust parameters, reducing the processing time of these layers from c to c / 2. The task is to determine the minimum number of operations needed to ensure that the computational time of all layers is odd.

Example 1

Input:

computationalTime = [2, 4, 8, 16]

Output:

4

Explanation: The optimal approach is:

• Choose c = 16 and reduce the computation time of layer 4 to 8. Thus, computationalTime = [2, 4, 8, 8].
• Choose c = 8 and reduce the computation time of layers 3 and 4 to 4. Thus, computationalTime = [2, 4, 4, 4].
• Choose c = 4 and reduce the computation time of layers 2, 3 and 4 to 2. Thus, computationalTime = [2, 2, 2, 2].
• Choose c = 2 and reduce the computation time of all the layers to 1. Thus, computationalTime = [1, 1, 1, 1]. The number of operations applied = 4. Thus, the answer returned is 4.

解法

每次操作把当前所有等于 c 的层除以 2。最优次数 = 各层独立去掉所有 2 因子所需次数的和，但每次操作可同时处理所有当前 = c 的层，故实际是"所有层的最大 v2(x) 累加 ... 等等"——其实关键观察：同一时刻所有 == c 的层一起被减半。所以答案 = 各元素去除 2 因子所需次数之和(因为不同元素的 trailing zero 序列可被分开计；同 c 的合并不影响计数)——更准确说：所有元素 2 因子总数之和。把每个数除尽 2 求 v2 累加。时间 O(n log max)。

from typing import List

def minimize_computation_time(computational_time: List[int]) -> int:
    ops = 0
    for x in computational_time:
        while x > 0 and x % 2 == 0:
            ops += 1
            x //= 2
    return ops

class Solution {
    public int minimizeComputationTime(int[] computationalTime) {
        int ops = 0;
        for (int x : computationalTime) {
            while (x > 0 && (x & 1) == 0) { ops++; x >>= 1; }
        }
        return ops;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minimizeComputationTime(vector<int>& computationalTime) {
        int ops = 0;
        for (int x : computationalTime) while (x > 0 && (x & 1) == 0) { ops++; x >>= 1; }
        return ops;
    }
};

There is a straight line of students of various heights. The students' heights are given in the form of an array, in the order they are standing in the line. Consider the region of a student as the length of the largest subarray that includes that student's position, and in which that student's height is equal to maximum height among all students present in that subarray. Return the sum of the region of all students. Function Description Complete the function sumOfSubarrayRegions in the editor. sumOfSubarrayRegions has the following parameter:

• int[] heights: an array of integers representing the heights of students Returns int: the sum of the lengths of all regions of all students

Constraints

• 1 ≤ heights.length ≤ 10^5
• 1 ≤ heights[i] ≤ 10^9

Example 1

Input:

heights = [3, 5, 6]

Output:

6

Explanation: For example-

• The longest subarray in which the first student's height is equal to the maximum height among all other students is [3]; thus, the length of the region of the first student is 1.
• The longest subarray in which the second student's height is equal to maximum height among all other students is [3, 5]; thus, the length of the region of the second student is 2.
• The longest subarray in which the third student's height is equal to the maximum height among all other students is [3, 5, 6]; thus, the length of the region of the third student is 3.
• Thus, the sum of the lengths of all regions of all students is 1 + 2 + 3 = 6.

解法

单调栈：对每个 i 找到左侧最近"严格更大"的下标 L(不存在则 -1)，右侧最近"严格更大"的下标 R(不存在则 n)。区间长度 = R − L − 1，累加。时间 O(n)。

from typing import List

def sum_of_subarray_regions(heights: List[int]) -> int:
    n = len(heights)
    left = [-1] * n
    right = [n] * n
    stack: List[int] = []
    for i in range(n):
        while stack and heights[stack[-1]] < heights[i]:
            right[stack.pop()] = i
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    return sum(right[i] - left[i] - 1 for i in range(n))

class Solution {
    public long sumOfSubarrayRegions(int[] heights) {
        int n = heights.length;
        int[] left = new int[n], right = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && heights[st.peek()] < heights[i]) right[st.pop()] = i;
            left[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }
        while (!st.isEmpty()) right[st.pop()] = n;
        long total = 0;
        for (int i = 0; i < n; i++) total += (long)(right[i] - left[i] - 1);
        return total;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long sumOfSubarrayRegions(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n, -1), right(n, n);
        vector<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.back()] < heights[i]) { right[st.back()] = i; st.pop_back(); }
            left[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }
        long long total = 0;
        for (int i = 0; i < n; i++) total += (long long)(right[i] - left[i] - 1);
        return total;
    }
};