NumberFactory 2.0

H. NumberFactory 2.0

No Submission Yet

Problem Statement

You are again invited to LHS's top-secret facility, the number factory, as an inspector. However, different from last year, the number factory has received a massive upgrade by Egor :O! Instead of a monotonous line, the factory is now in the shape of a tree with \(N\) nodes rooted at node \(1\). Furthermore, instead of the boring \(+\), \(-\), and \(\times\) operations, we now have the much more interesting bitwise operations: XOR, AND, OR. More specifically, each leaf node is assigned a number \(a_i\), and each non-leaf node is assigned one of [XOR, AND, OR] as its operator \(b_i\). The value of leaf node \(i\) is just its assigned number \(a_i\), whereas the value of a non-leaf node is the "sum" of all its children's values under the operator \(b_i\). For example if \(c_1\), \(c_2\), \(c_3\) are \(v\)'s children, and \(v\)'s operator is XOR, then its value is \(c_1\) XOR \(c_2\) XOR \(c_3\).

Of course, as an inspector, you want to make sure all components of the factory are working properly, so you have \(M\) queries of three types to perform. The first type asks what the value of node \(q_i\) is. The second type changes the operator of non-leaf node \(q_i\)'s operator to \(o_i\). The third type changes the assigned number of node \(q_i\) to \(x_i\). Note that any modification to node \(i\) might cause other nodes to recalculate their values as well, such as its parent, and its parent's parent.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 128mb


\(2 \leq \sum M, N \leq 2 \cdot 10^5\) and \(0 \leq a_i \leq 10^9\)

Input format

The first line contains integer \(T\), the number of testcases. For each testcase, the first line contains \(2\) numbers \(N\), \(M\).
The following \(N\) lines describe the nodes, where line \(i\) describes node \(i\), containing 3 strings \(x\), \(y\), \(z\):
- if \(x = 0\), it is not a leaf node. \(y\) is its parent node(with the exception for the first node, which in that case \(y\) is always 0), and \(z\) is one of [XOR, AND, OR]
- if \(x = 1\), it is a leaf node. \(y\) is its parent node, and \(z\) is its assigned number \(a_i\).
The next \(M\) lines each describe a query. Let \(c\) be the first character:
- if \(c = Q\), it is the first type of query. The following number is \(q_i\) and you have to output the corresponding node's current value.
- if \(c = R\), it is the second type of query. The following two variables are \(x\) and \(y\), where you change non-leaf node \(x\)'s operator to \(y\).
- if \(c = M\), it is the third type of query. The following two numbers are \(x\) and \(y\), where you change leaf node \(x\)'s assigned number \(a_x\) to \(y\).

Output format

For each query of the first type, output node \(q_i\)'s current value after all the prior modifications.

Sample input:

6 5
0 0 XOR
1 1 3
0 1 OR
1 1 1
1 3 0
1 3 5
Q 3
M 2 3
M 6 6
Q 1

Sample output


Sample Explanation

For the first query of the first type, node \(3\)'s value is the OR of nodes \(5\) and \(6\)'s values, \(5\) OR \(0 = 5\).
For the second query, node \(3\)'s value is the XOR of node \(5\) and node \(6\)'s values, \(6\) XOR \(0 = 6\). Subsequently, node \(1\)'s value is the XOR of nodes \(2\), \(3\), and \(4\)'s values, \(3\) XOR \(6\) XOR \(1 = 4\).

Contact Us
LIT Discord Server