355. Bishu and Soldiers

Bishu has an army of n soldiers, each with a certain power, and fights q rounds. In round i his power is M(i); with it he defeats every soldier whose power is at most M(i) (all defeated soldiers respawn before the next round, so every round starts with the same n soldiers). For every round, in order, print how many soldiers Bishu defeats and the sum of their powers; print all of these numbers for all q rounds, space-separated, on a single line.

Input: The first line contains an integer n. The second line contains n space-separated integers, the soldiers' powers. The third line contains the integer q. The fourth line contains q space-separated integers, the M value for each round. Output: Print, for every round in order, the count and sum of defeated soldiers' powers, all space-separated on a single line.

1 <= n, q <= 10^5, 1 <= soldier power, M(i) <= 10^9

The soldiers respawning before each round (so every round starts fresh) is exactly why the SAME preprocessed sorted array and prefix sums can be reused for every single query, without needing to rebuild anything between rounds.

For each of several rounds with a given power threshold, count how many soldiers Bishu defeats (those with power at most the threshold) and the sum of their powers. Brute force: For every query, scan through all n soldiers directly, checking each against the threshold and summing matches - this costs O(n) per query, giving O(n*q) overall, too slow for large n and q. Optimised: Sorting once and building a prefix-sum array ONCE upfront lets every subsequent query be answered with a single binary search (O(log n)) plus an O(1) prefix-sum lookup - turning what would be O(n) per query into O(log n) per query.

For each of the q rounds, scan through all n soldiers, and for every soldier whose power is at most M(i), add one to the defeated count and add their power to the running sum. Print the count and sum for that round before moving to the next. This directly follows the problem statement but redoes a full O(n) scan for every single round, which is wasteful since the same soldier list is reused unchanged every round. Time: O(n*q) Space: O(1)

Sort the soldiers' powers once and build a prefix-sum array over the sorted powers. For each round, binary search for the rightmost index whose power is at most M(i); that index directly gives both the count (index + 1) and, via a single prefix-sum lookup, the total power of all defeated soldiers, both in O(log n) per round. This eliminates the per-round linear summation entirely, so the whole solution runs in time proportional to sorting plus a logarithmic amount of work per query, which is optimal given that comparison-based sorting is required to enable the binary search in the first place. Time: O((n+q) log n) Space: O(n)

Sort the soldiers' powers once up front. For each round, binary search for the rightmost position where power <= M(i), which immediately gives the count of defeated soldiers in O(log n). However, without any further precomputation, getting the sum of those defeated soldiers' powers still requires summing that prefix element by element, so the sum computation remains linear in the number of defeated soldiers. This is a real improvement in isolating the count quickly but doesn't yet fix the cost of computing sums. Time: O(n log n + n*q) Space: O(n)

1. Sort the soldiers' powers once, and build a prefix-sum array over this sorted list. 2. For each query threshold M, binary search for how many sorted powers are <= M - that count is directly the answer's first part. 3. The matching prefix sum (up to that count) is directly the sum of their powers - the answer's second part.

Time: O(n log n) for the initial sort, plus O(q log n) for all the queries combined. Space: O(n), for the sorted array and its prefix-sum array.

Test an M smaller than every soldier's power (0 defeated), an M at least as large as the maximum power (all defeated), and n = q = 10^5 for performance.

Be ready to explain the general 'preprocess once (sort + prefix sums), then answer each query with binary search' pattern - a widely reusable technique whenever the SAME underlying dataset is queried repeatedly with different thresholds.