Stack and Queue
Contest: Kotlin Heroes: Episode 11
Tags: *special, data structures, divide and conquer

There are $$$2$$$ queues of patients at the doors of two doctors. The first doctor sees patients in the usual order of the queue — whoever arrived first will be seen first. The second doctor does the opposite — he sees those who arrived last first. Thus, there is a queue for the first doctor and a stack for the second doctor. A patient can be in both the queue and the stack. Each patient is characterized by the time their visit to the doctor will take (the time is the same for both doctors).

When the appointments begin, the doctors will see patients in the order of the queue and stack, respectively. As soon as a doctor finishes with one patient, he will call the next one.

But there is one problem: if a patient is in both the queue and the stack, and he is called to one doctor first and then to the other, while he has not yet finished with the first one, confusion will arise. It is allowed for a patient to go to the second doctor at the exact moment he finishes with the first doctor.

The current configuration of the queue and stack is called good if the doctors can see all the patients without any confusion arising.

Initially, both the queue and the stack are empty. There are three types of queries:

1. add patient $$$x$$$ to the queue;
2. add patient $$$x$$$ to the stack;
3. patient $$$x$$$, who was in the queue, realizes he is in the wrong place and moves to the stack; however, he moves to the position in the stack as if he had entered the stack at the moment of the query when he entered the queue.

It is guaranteed that after each query, each patient is no more than once in the queue and no more than once in the stack.

After each query, you need to determine if the current configuration is good.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of requests.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — for each patient, the time their visit to the doctor will take.

Each of the following $$$n$$$ lines contains two integers $$$t$$$ and $$$x$$$ ($$$1 \le t \le 3$$$; $$$1 \le x \le n$$$) — the type of query and the patient's index. It is guaranteed that:

- if the query is of type $$$1$$$, then patient $$$x$$$ is not in the queue yet;
- if the query is of type $$$2$$$, then patient $$$x$$$ is not in the stack yet;
- if the query is of type $$$3$$$, then patient $$$x$$$ is in the queue already and not in the stack yet.

Output format:
After each query, print "YES", if the current configuration is good, and "NO" otherwise.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test, there are the following configurations:

1. queue: $$$[1]$$$; stack: $$$[]$$$; patient $$$1$$$ is seen by the first doctor for $$$10$$$ minutes, starting at minute $$$0$$$.
2. queue: $$$[1]$$$; stack: $$$[1]$$$; patient $$$1$$$ is seen by the first doctor during $$$[0; 10)$$$ and by the second during $$$[0; 10)$$$. Since patient $$$1$$$ must be at both doctors at the same time, the answer is "NO".
3. queue: $$$[1]$$$; stack: $$$[1, 2]$$$; patient $$$1$$$ is seen by the first doctor during $$$[0; 10)$$$, and by the second during $$$[15; 25)$$$; patient $$$2$$$ is seen by the second doctor during $$$[0, 15)$$$. Now patient $$$1$$$ can make it to the second doctor after seeing the first.

In the second test, the configuration after query $$$4$$$ is as follows:

- queue: $$$[1, 2]$$$;
- stack: $$$[5, 3]$$$;
- patient $$$1$$$: first doctor $$$[0, 2)$$$, second doctor is not seeing him;
- patient $$$2$$$: first doctor $$$[2, 7)$$$, second doctor is not seeing him;
- patient $$$3$$$: first doctor is not seeing him, second doctor $$$[0, 1)$$$;
- patient $$$5$$$: first doctor is not seeing him, second doctor $$$[1, 6)$$$.

After request $$$5$$$, the next configuration is:

- queue: $$$[1]$$$;
- stack: $$$[5, 2, 3]$$$;
- patient $$$1$$$: first doctor $$$[0, 2)$$$, second doctor is not seeing him;
- patient $$$2$$$: first doctor is not seeing him, second doctor $$$[1, 6)$$$;
- patient $$$3$$$: first doctor is not seeing him, second doctor $$$[0, 1)$$$;
- patient $$$5$$$: first doctor is not seeing him, second doctor $$$[6, 11)$$$.

After request $$$6$$$, the next configuration is:

- queue: $$$[1, 2]$$$;
- stack: $$$[5, 2, 3]$$$;
- patient $$$1$$$: first doctor $$$[0, 2)$$$, second doctor is not seeing him;
- patient $$$2$$$: first doctor $$$[2, 7)$$$, second doctor $$$[1, 6)$$$;
- patient $$$3$$$: first doctor is not seeing him, second doctor $$$[0, 1)$$$;
- patient $$$5$$$: first doctor is not seeing him, second doctor $$$[6, 11)$$$.

Patient $$$2$$$ must be at both doctors at the same time.

After request $$$7$$$, the next configuration is:

- queue: $$$[2]$$$;
- stack: $$$[1, 5, 2, 3]$$$;
- patient $$$1$$$: first doctor is not seeing him, second doctor $$$[11, 13)$$$;
- patient $$$2$$$: first doctor $$$[0, 5)$$$, second doctor $$$[1, 6)$$$;
- patient $$$3$$$: first doctor is not seeing him, second doctor $$$[0, 1)$$$;
- patient $$$5$$$: first doctor is not seeing him, second doctor $$$[6, 11)$$$.

Patient $$$2$$$ must be at both doctors at the same time.

Example input:
3
10 15 4
1 1
2 1
2 2

Example output:
YES
NO
YES

Example input:
7
2 5 1 5 5 4 8
1 1
2 5
1 2
2 3
3 2
1 2
3 1

Example output:
YES
YES
YES
YES
YES
NO
NO

Editorial:
Consider the time intervals for a certain patient at both doctors. Let these be $$$[l_1; l_1 + a_i)$$$ and $$$[l_2; l_2 + a_i)$$$. How can we check if the configuration is good? For each patient, we need to ensure that these intervals do not overlap.
Then it makes sense to take the following step. Let's change the order of computation. Instead of checking the validity for all patients at each moment of time, let's find the moments of time when the intervals for each patient overlap.
First, let's forget about queries of the third type. Suppose patients can only be added to a queue or a stack.
Here we can get this idea. The moments of time when the intervals of a certain patient overlap are consecutive, thus forming a segment of queries. Suppose a patient arrives earlier in the queue than in the stack. When he arrives in the queue, his interval $$$[l_1; l_1 + a_i)$$$ is defined, and no later queries will affect this interval. Then he arrives in the stack, and his interval in the stack becomes $$$[0; a_i)$$$. As more people arrive in the stack, his second interval will move further to the right. Accordingly, at some point, it will start overlapping with the first interval, and then it will be to the right of it and will never overlap again. The analysis for the case when the patient arrives in the stack earlier is similar.
Thus, we can solve the problem using binary search. We will collect all queries of the second type into a separate array and build a prefix sum on it. For each patient, we will find the first moment of time when his second interval starts overlapping with the first. Then we will find the last such moment of time. We will say that between these queries, the answer is "NO". This can be done using a difference array. Suppose we have to say "NO" for the segment from $$$l$$$ to $$$r$$$. We will increase $$$\mathit{dt}_l$$$ by $$$1$$$, decrease $$$\mathit{dt}_{r+1}$$$ by $$$1$$$, and collect the prefix sum over the array $$$\mathit{dt}$$$. Now all values from $$$l$$$ to $$$r$$$ inclusive are equal to $$$1$$$, while the others are equal to $$$0$$$. First, we will perform the additions and subtractions for all patients, then we will collect the prefix sum once at the end and output "YES" if $$$\mathit{dt}_i$$$ is equal to $$$0$$$ and "NO" otherwise.
Let's bring the queries of the third type back. What if such monotonicity still holds? Let's check. If the third query is applied to a patient, then one of his intervals is still undefined, so there is nothing to analyze. However, such movement affects the intervals of other patients. Since he leaves the queue, the intervals of patients in the queue after him move left by $$$a_i$$$. And since they are placed somewhere in the stack, the intervals of patients in the stack after him move right by $$$a_i$$$. Thus, the relative positioning of the intervals is still monotonic.
Great, so we can still apply binary search. However, it is not so straightforward to do now.
We will use the technique of parallel binary search. For each patient, we will store the boundaries of his binary search. At each iteration, we will simulate all queries and learn to ask at certain moments what intervals the patient has. For each patient, let's ask at the middle point of his binary search boundaries and save the new boundaries for the next iteration. If patients are stored in increasing order of their middle point, we can simulate queries with two pointers.
How to ask for the segments? We will create a data structure that maintains the prefix sum of patients in the queue and in the stack. When a patient arrives in the queue, let's add him to the structure for the queue, as well as create an empty spot for him in the stack and add $$$0$$$ to the stack. He will occupy this spot when the third type query is applied to him. When a patient arrives in the stack, we simply add him to the structure for the stack. When the third type query occurs, we will assign $$$0$$$ to his spot in the queue in the structure for the queue, and assign $$$a_i$$$ to the occupied spot in the stack in the structure for the stack. Now we can query both intervals in $$$O(\log n)$$$ using a mass sum query. For such queries, we can use a BIT.
Thus, we will perform $$$O(\log n)$$$ iterations of the external parallel binary search. Inside the iteration, we will apply all $$$n$$$ queries and ask for each patient once. Therefore, one iteration takes $$$O(n \log n)$$$.
Overall complexity: $$$O(n \log^2 n)$$$.
Alternatively, we can write parallel binary search using the "divide and conquer" approach. We will write a function $$$\mathit{calc(l, r, ids)}$$$ that maintains the indices of patients whose binary search boundaries take values $$$[l; r)$$$.
Upon entering the function, we will maintain the invariant that queries from $$$0$$$ to $$$l$$$ (not inclusive) have already been applied. The process is as follows. Let $$$\displaystyle m = \lfloor\frac{l + r}{2}\rfloor$$$. We will apply queries from $$$l$$$ to $$$m$$$ (not inclusive) in the same way as in the first solution. Then we will go through the patients from the list $$$\mathit{ids}$$$ and make a query for their intervals. Based on the results of the query, we will understand the new boundaries of the binary search. Accordingly, we will distribute patients into those who go into the recursive call $$$[l; m)$$$ and those who go into $$$[m; r)$$$. Then we will solve the problem recursively on $$$[m; r)$$$ (since queries from $$$0$$$ to $$$m$$$ are now applied). After that, we will roll back the changes made by applying queries from $$$l$$$ to $$$m$$$. Finally, we will solve the problem recursively on $$$[l; m)$$$.
Overall complexity: $$$O(n \log^2 n)$$$.