Fleet capacity after server id replacements

A service runs on a fleet of n servers. Each server has an integer id, and a server with id x can handle x requests at a time. The fleet's total capacity is the sum of all server ids.

Servers are swapped out for maintenance, one batch per day. On day j, every server whose id is currently replaced[j] is replaced by a server with id new_id[j]. Servers that received a new id on an earlier day count under their new id. If no server has id replaced[j], nothing changes that day.

Implement:

def get_total_requests(server: list[int], replaced: list[int], new_id: list[int]) -> list[int]

Return a list whose j-th entry is the fleet's total capacity at the end of day j.

Constraints

• 1 <= n <= 10^5, 0 <= q = len(replaced) = len(new_id) <= 10^5
• 1 <= server[i], replaced[j], new_id[j] <= 10^9
• Totals can exceed 32 bits.

Example 1

server   = [4, 4, 9]
replaced = [4, 9, 2]
new_id   = [7, 2, 6]
output   = [23, 16, 20]

Day 1: both 4s become 7, so the fleet is [7, 7, 9] = 23. Day 2: the 9 becomes 2, giving [7, 7, 2] = 16. Day 3: the 2 becomes 6, giving [7, 7, 6] = 20.

Example 2

server   = [3, 3]
replaced = [3, 5]
new_id   = [5, 1]
output   = [10, 2]

The servers renamed to 5 on day 1 are replaced again on day 2.

An O(n * q) simulation is too slow at these limits. Aim for O(n + q).