Solve three C++ algorithmic tasks
Solve the following three C++ algorithmic tasks. For each, implement an efficient function and state time and space complexity.
a) Diminishing prices revenue: Given an array inventory where inventory[i] is the initial sale price for type i, each time you sell one unit of a type, the next sale price for that type decreases by 1 down to 0. You must perform exactly orders sales across all types to maximize total revenue. Return revenue modulo 1_000_000_007. Constraints: 1 <= inventory.size() <= 2e5, 1 <= orders <= 1e13, 1 <= inventory[i] <= 1e9. Target: O(n log max(inventory)) or better.
b) Count subarrays with fixed bounds: Given an integer array nums and two integers minVal and maxVal (minVal <= maxVal), count the number of subarrays whose minimum equals minVal and whose maximum equals maxVal. Constraints: 1 <= nums.size() <= 2e5, -1e9 <= nums[i] <= 1e9. Target: O(n) time, O(
- extra space.
c) Binary matrix row-equivalence under column flips: Given a binary matrix A with n rows and m columns (toggling a column flips that bit in every row), two rows are equivalent if one can be transformed into the other by flipping any subset of columns. Count the number of unordered pairs of equivalent rows. Return a 64-bit integer. Constraints: 1 <= n <= 1e5, 1 <= m <= 30. Target: O(n * m / 64) or better using hashing/bitmasks.