Seat Booking Ranges

Medium · prefix sum

A cinema row has n seats, numbered 1 to n, and every seat starts empty. You are given ops, a list of actions in the order they happen. Each action is a list of whole numbers, and its first number says what kind of action it is:

[1, i] books seat i. If seat i is already booked, nothing changes.
[2, i] cancels the booking of seat i. If seat i is empty, nothing changes.
[3, l, r] asks how many seats numbered from l to r, both included, are booked right now.

Return a list with the answer to every [3, l, r] action, in the order those actions appear.

Examples

Example 1

Input: n = 5, ops = [[1, 2], [1, 4], [3, 1, 5], [2, 2], [3, 1, 3]]

Output: [2, 0]

Seats 2 and 4 are booked, so the first count is 2. After seat 2 is cancelled, seats 1 to 3 hold no bookings.

Example 2

Input: n = 3, ops = [[1, 1], [1, 1], [3, 1, 1], [2, 2], [3, 1, 3]]

Output: [1, 1]

Booking seat 1 a second time changes nothing, and cancelling empty seat 2 changes nothing, so both counts are 1.

Example 3

Input: n = 1, ops = [[3, 1, 1]]

Output: [0]

Nothing has been booked yet.

Constraints

1 <= n <= 10^4
1 <= len(ops) <= 10^4
Every action is [1, i], [2, i] or [3, l, r]
1 <= i <= n and 1 <= l <= r <= n