Queries for the Array
Contest: Educational Codeforces Round 154 (Rated for Div. 2)
Difficulty rating: 1600
Tags: data structures, dfs and similar, implementation, strings, trees

Monocarp had an array $$$a$$$ consisting of integers. Initially, this array was empty.

Monocarp performed three types of queries to this array:

- choose an integer and append it to the end of the array. Each time Monocarp performed a query of this type, he wrote out a character +;
- remove the last element from the array. Each time Monocarp performed a query of this type, he wrote out a character -. Monocarp never performed this query on an empty array;
- check if the array is sorted in non-descending order, i.,e. $$$a_1 \le a_2 \le \dots \le a_k$$$, where $$$k$$$ is the number of elements in the array currently. Every array with less than $$$2$$$ elements is considered sorted. If the array was sorted by the time Monocarp was performing that query, he wrote out a character 1. Otherwise, he wrote out a character 0.

You are given a sequence $$$s$$$ of $$$q$$$ characters 0, 1, + and/or -. These are the characters that were written out by Monocarp, given in the exact order he wrote them out.

You have to check if this sequence is consistent, i. e. it was possible for Monocarp to perform the queries so that the sequence of characters he wrote out is exactly $$$s$$$.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one line containing the string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$). This string consists of characters 0, 1, + and/or -. This is the sequence of characters written by Monocarp, in the order he wrote them.

Additional constraints on the input:

- for every prefix of $$$s$$$, the number of characters + on it is not less than the number of characters - on it. In other words, if Monocarp actually performed these queries, he would never try to remove the last element from the empty array;
- the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print YES if it was possible for Monocarp to perform the queries so that the sequence of characters he wrote is exactly $$$s$$$. Otherwise, print NO.

You can print each letter in any register.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Monocarp could perform the following sequence of queries:

- add the integer $$$13$$$;
- add the integer $$$37$$$;
- check that the current array $$$[13, 37]$$$ is sorted in non-descending order (and it is sorted).

In the fifth test case, Monocarp could perform the following sequence of queries:

- add the integer $$$3$$$;
- add the integer $$$2$$$;
- check that the current array $$$[3, 2]$$$ is sorted (it is not);
- remove the last element;
- add the integer $$$3$$$;
- check that the current array $$$[3, 3]$$$ is sorted (it is);
- remove the last element;
- add the integer $$$-5$$$;
- check that the current array $$$[3, -5]$$$ is sorted (it is not).

In all other test cases of the example test, it is impossible for Monocarp to write the sequence $$$s$$$ when performing the queries according to the statement.

Example input:
7
++1
+++1--0
+0
0
++0-+1-+0
++0+-1+-0
+1-+0

Example output:
YES
NO
NO
NO
YES
NO
NO

Editorial:
First of all, let's analyze which situations cause the answer to be NO. There are two types:
• if the number of elements in the array is currently less than $$$2$$$, the array is definitely sorted. So, if we get a 0 and the number of elements is $$$0$$$ or $$$1$$$, the answer is NO;
• if the array is sorted, but some prefix of it (maybe coinciding with the whole array) is not sorted, this is also a NO.
These are the only two situations that cause a NO. We can prove that if none of this occurs, the answer is YES, using the following construction: every time there is a + query, we will add $$$1$$$ to the array; every time there is a 0 query, and the current array is sorted, we will change the last element of the array to $$$0$$$ (and assume we added $$$0$$$ instead of $$$1$$$ in the query it was added). That way, we can ensure that the array stays sorted as long as possible. The only cases when this construction doesn't work are:
• we try to change an element to $$$0$$$, but there is no such element (the array is empty), or the array stays sorted after the change (we change the first element). This is exactly when a query 0 appears and the current number of elements is less than $$$2$$$;
• we change an element to $$$0$$$, and it makes the current array non-sorted, but it has to be sorted due to a query of type 1 affecting it. This is exactly when we have a sorted array with a non-sorted prefix.
Okay, now we have to check these two conditions somehow. The first one is quite easy: just keep track of the number of elements in the array; every time you process +, increase it; every time you process -, decrease it; every time you process 0, check the number of elements.
The second condition is tricky. There are many approaches on how to handle it; I will describe two of them.
Approach $$$1$$$ (Roms)
We are interested in a situation when a sorted array has an unsorted prefix. Suppose there is a state of our array when this happens. In case when this array has multiple prefixes for which we know that they are sorted, which one should we choose? It should be the longest sorted prefix, because we want an unsorted prefix to be shorter (or have the same length). And among all non-sorted prefixes, we are interested in the shortest one, for the same reason.
So, let's go over the queries and keep track of the shortest non-sorted prefix and the longest sorted prefix of our array. Let's analyze how our queries affect these two values.
• when we append a new element (query of type +), we no longer know that the current array is sorted, but its longest sorted prefix stays the same, and its shortest non-sorted prefix also stays the same. So, we don't need to update these values;
• when we delete the last element (query of type -), the length of the sorted prefix might change. If it was equal to the number of elements before the query, it should decrease by $$$1$$$, because the last element on that prefix was deleted, and the prefix no longer exists. As for the length of the shortest unsorted prefix, if it was equal to the number of elements in the array before the query, it should be set to $$$0$$$ — because maybe the last element of the array made the array unsorted, and we don't know anything about the prefixes before it.
• when we process a query of type 0 or 1, we should update the shortest non-sorted prefix or the longest sorted prefix accordingly.
After each query, we can just check that the longest sorted prefix is shorter than the shortest non-sorted prefix (or one of them doesn't exist).
Approach $$$2$$$ (BledDest)
BledDest is a graph theory lunatic, so naturally, he designed a graph-related solution to this problem.
Let's visualize all states of the array using a rooted tree. Every moment of time after a query corresponds to some vertex in this tree, and one vertex $$$x$$$ is a parent of another vertex $$$y$$$ if the array in the state represented by $$$x$$$ is the same as the array represented by $$$y$$$, but without the last element. For example, if the string of queries is ++-++---+-+, the tree looks like this (the labels on the vertices correspond to the number of queries after which the array is in that state):
This tree can be constructed from the query string as follows. Start with the root vertex, which represents the state when the array is empty. Every time you get a query +, you need to go down the tree. You create a new vertex to go into, because if you go down the tree to an existing vertex, it means that the states will coincide — and the arrays in these two states are not necessarily similar. If you get a query -, you go up the tree — so you either maintain the current path in the tree in a stack, or store a parent for each vertex, to know where to go when you go up.
Okay, now what about queries of type 0 and 1? Every time we process such a query, we mark the current vertex to remember that it has a 0 or a 1 in it. For example, you can store two boolean arrays that give you the information whether a vertex is marked with 0 and whether a vertex is marked with 1.
So, how does this tree help us in solving the problem? Recall what we're trying to check: we want to find out if a sorted array has a non-sorted prefix. In terms of our tree, it means that a vertex marked with 0 has an ancestor (possibly itself) marked with 1. To check that in $$$O(n)$$$, you can, for example, run a series of DFS traversals from all vertices marked with 1 and make sure that you don't visit any vertices marked with 0. Or you could do it in a single DFS (as the model solution does) which, for each vertex in the tree, computes if it has a vertex marked with 0 in its subtree.