Customer Revenue System with Referrals and Top K Query

Problem: Customer Revenue System Design and implement a customer revenue system that supports adding customers, adding customers by referral, and querying the top K customers by revenue. Each customer has a unique integer customer_id, assigned increasingly from 0 in creation order. Each customer has three revenue metrics: own_revenue: revenue contributed by the customer itself. direct_revenue: the customer's own revenue plus the own revenue of all directly referred customers. nested_revenue: the customer's own revenue plus the own revenue of all descendants in its referral subtree. Support the following operations: ADD revenue Create a new customer without a referrer, with own_revenue = revenue. Print the new customer_id. REF referrer_id revenue Create a new customer directly referred by referrer_id, with own_revenue = revenue. The new customer becomes a direct child of referrer_id. Increase direct_revenue of referrer_id by revenue. Increase nested_revenue of referrer_id and all its ancestors by revenue. Print the new customer_id. TOP k Return the top k customer ids sorted by direct_revenue descending. If revenues tie, the smaller customer_id comes first. If there are fewer than k customers, return all customers. NTOP k Follow-up: return the top k customer ids sorted by nested_revenue descending. If revenues tie, the smaller customer_id comes first. If there are fewer than k customers, return all customers. Input Format The first line contains an integer q, the number of operations. The next q lines each contain one operation: ADD revenue REF referrer_id revenue TOP k NTOP k Output Format For ADD and REF, print the newly created customer_id. For TOP and NTOP, print one line of space-separated customer ids. If there are no customers, print an empty line. Constraints 1 <= q <= 2 * 10^5 1 <= revenue <= 10^9 1 <= k <= 10^5 In every REF operation, referrer_id is guaranteed to exist. Example Input: 6 ADD 10 ADD 20 REF 0 5 TOP 3 NTOP 2 TOP 10 Output: 0 1 2 1 0 2 1 0 1 0 2 Example Input 6 ADD 10 ADD 20 REF 0 5 TOP 3 NTOP 2 TOP 10 Output 0 1 2 1 0 2 1 0 1 0 2