P3968 [TJOI2014] Power Strip

There are many power strips in Xiao M’s lab. The outlets are indexed from $1$ to $n$, arranged in a line from left to right. Every morning, all outlets are unused. Each time a student comes to the lab, they plug their laptop’s power into some unused outlet. The students follow a peculiar rule: first, they find the longest contiguous segment of unused outlets. If there are multiple segments with the same length, they choose the rightmost one. Then they plug into the middle of that segment. If the segment length is even, they pick the right middle position (i.e., the right one). When a student leaves the lab, they unplug their power. It is guaranteed that whenever a student arrives, there is at least one empty outlet. You need to answer how many outlets are already in use within the interval $[l,r]$.

The first line contains two integers $n$ and $q$, the number of outlets and the number of queries. Then follow $q$ lines. Each line starts with an integer $k$. > If $k$ is $0$, it is followed by two integers $l$ and $r$, indicating a query. > > Otherwise, $k$ indicates that the student with ID $k$ arrives or leaves. The $1$st appearance of $k$ means arrival, the $2$nd appearance means departure, and so on. Each student ID is unique.

For each query, output one integer: the number of outlets already in use within the query interval.

Constraints For $30\%$ of the testdata, $n \le 10^5, q \le 10^3$. For $100\%$ of the testdata, $1 \le n \le 10^9, 1 \le q \le 10^5, 0 \le k \le 10^9, 1 \le l \le r \le n$. Translated by ChatGPT 5