A deli hands out numbered tickets 1 .. n at opening time, one ticket per party (a family of four gets one ticket), and parties are served in ticket order. While they wait, people drift away: a kid goes back to the car, a couple gives up on lunch. The screen above the counter lets anyone type their ticket number and see how many people are still ahead of them.
Implement DeliLine(party_sizes), where ticket t starts with party_sizes[t - 1] people, with:
leave(t, k) -> None:kpeople from partytwalk away. It's guaranteed that1 <= k <=the party's current size. A party that drops to 0 people is simply empty.people_ahead(t) -> int: the total number of people still waiting in parties with tickets1 .. t - 1.
line = DeliLine([2, 4, 1, 3]) # parties: #1=2, #2=4, #3=1, #4=3
line.people_ahead(4) # 7 (2 + 4 + 1)
line.leave(2, 3) # party #2 now has 1 person
line.people_ahead(4) # 4
line.leave(1, 2) # party #1 is empty
line.people_ahead(3) # 1
line.people_ahead(1) # 0 (nobody is ever ahead of ticket 1)
Constraints: 1 <= n <= 10**5, party sizes are between 1 and 20, 1 <= t <= n, up to 10**5 calls in total. Adding up the parties ahead on each call (sum(sizes[:t-1])) is O(n) per call, about 10**10 steps in the worst case; each call must be O(log n).
Show hint
keep a Fenwick tree over tickets holding each party's current size. leave is add(t, -k) and people_ahead(t) is prefix_sum(t - 1). You can build the tree in O(n log n) by calling add once per party.