OA: Customer revenue system

A SaaS company tracks how much money each customer brings in. Customers can be referred by an existing customer, and a referrer is rewarded with credit for everything their direct referrals spend. Build RevenueSystem:

• add_customer(revenue: int, referrer_id: int | None = None) -> int: register a new customer whose first purchase is revenue, and return their ID. IDs are 0, 1, 2, ... in registration order. If referrer_id is given, the new customer was referred by that customer. Raise ValueError if referrer_id doesn't exist.
• add_revenue(customer_id: int, amount: int) -> None: the customer spends amount more. Raise ValueError for an unknown ID.
• total_revenue(customer_id: int) -> int: the customer's own spending plus everything spent (ever, including first purchases) by the customers they directly referred. Referrals of referrals do not count. Raise ValueError for an unknown ID.
• lowest_k(k: int, min_total: int) -> list[int]: up to k customer IDs whose total revenue is strictly greater than min_total, ordered by total revenue ascending, ties by smaller ID. Returns fewer if fewer qualify.

All amounts are integers >= 0.

rs = RevenueSystem()
rs.add_customer(20)            # 0
rs.add_customer(15, 0)         # 1   referred by 0
rs.add_customer(5, 1)          # 2   referred by 1
rs.add_revenue(2, 10)          #     customer 2 has now spent 15 in all
rs.total_revenue(0)            # 35  own 20 + customer 1's 15 (customer 2 is not a direct referral of 0)
rs.total_revenue(1)            # 30  own 15 + customer 2's 15
rs.total_revenue(2)            # 15  referred nobody
rs.lowest_k(2, 15)             # [1, 0]     totals 30 and 35; customer 2's 15 is not > 15
rs.lowest_k(5, 0)              # [2, 1, 0]
rs.lowest_k(0, 0)              # []

Scale: up to 20,000 customers, and tens of thousands of add_revenue and lowest_k calls mixed together, with small k. Sorting every customer on each lowest_k call is too slow: keep the customers ordered by total as the totals change.