Description
In this problem, you are given a prefix Boolean expression, which has at most N=10^5 variables and 2 kinds of operators ‘&’ and ‘|’. Each variable has an ID number. The values of these variables can be either 0 or 1, and are all initialized as 0.
You will be given M ID numbers. For each ID number, you should flip (0 will become 1, 1 will become 0) the value of the corresponding variable and then compute/output the result of the prefix Boolean expression.
Example:
Assume the prefix Boolean expression is &[1][2] and the given ID numbers are “2 1”. First the value of variable 2 will change from 0 to 1. The output of &[1][2] is 0&1=0. Next, the value of variable 1 will change from 0 to 1. The output of &[1][2] is 1&1=1.
Hint: (You can go to the Input/Output description directly, and come back for hints if necessary.)
Hint 1: To solve this problem, you can parse the input and derive the output recursively each time a variable is flipped. Unfortunately, this brute-force approach is not efficient and can lead to TLE, in particular the 3rd and 4th testcases in this problem. We encourage you to use the syntax tree of the prefix Boolean expression for better efficiency.
Hint 2: The key idea behind the syntax-tree approach is to avoid re-evaluation of the whole expression every time a bit is flipped. Some more hints are provided for you as follows:
- [Data structure] Use a tree node pointer array to record the address of each variable (leaf) node of the syntax tree: you can locate each variable to be flipped directly;
- [Data structure] For each tree node i, record the value of its subtree (rooted at node i);
- [Algorithm] Starting from the variable node to be flipped, move upward following the syntax tree and update the node values until the output of the syntax tree (or the Boolean expression) can be determined.
Example:
Consider the following syntax tree for "|&|[1][2][3][4]". Assume [1] is flipped. You will find that the value of node A should be changed to 1|0=1. Moreover, you note that the value of B remains unchanged, i.e., 1&0=0, and the checking process can stop.
Later, when [3] is flipped, both the values of node B and the root node should be changed. In this case, the output is also changed.
Sample structure:
typedef struct node{
int value; // This is the value of the subtree, not the ID number
int tokentype;
struct node *leftchild;
struct node *rightchild;
struct node *parent; //pointing to the parent node
}Node;
Node* variable[100001]; // This array stores the pointers pointing to the tree nodes. For example, variable[0] points to the node with ID number 0.
Input
The first line has one number T, 0<T<= 7, indicating the number of testcases.
The following lines are the inputs of the testcases.
Each testcase contains three lines:
1. N, M (0<N<=100000, indicating the number of variables in a given prefix Boolean expression. 0<M<=100000, indicating how many times the values are flipped).
2. A string S, describing the prefix Boolean expression (& means and gate, | means or gate, [i] means a variable ID)
3. M numbers, where each number i means the value of variable i is flipped. The order matters.
Note that all the variables are initially 0.
Each ID number only appears once in the prefix Boolean expression.
The depth of the tree is no more than 30.
Output
For each testcase, you should output M lines, each showing the output of the prefix Boolean expression after a variable is flipped.
0 for false, 1 for true.