P7982 [JRKSJ R3] Qinqin's Tree

Qinqin has a binary tree that satisfies: - The tree has infinitely many nodes. - Each node has an index and a weight. Initially, the weight of every node is $0$. - The root node has index $1$. - If a node has index $i$, then its left and right children have indices $2i$ and $2i+1$, respectively. Qinqin will perform a total of $m$ operations on the tree. Each operation is one of the following: 1. Add $v$ to the weight of every node in the subtree rooted at the node with index $x$. 2. Query the sum of weights of all nodes on the path from the node with index $x$ to the node with index $y$ in the tree. The answer is taken modulo $2^{32}$. However, Qinqin will not directly give $x$ and $y$. Instead, she gives a $01$ sequence $a$ of length $n$. Each time she needs to give $x$ or $y$, she provides an interval $[l_x,r_x]$ or $[l_y,r_y]$. The number is the value of this interval interpreted as a binary number.

The first line contains two integers $n,m$.\ The second line contains a string of length $n$ representing $a$. It is guaranteed that the string contains only `0` and `1`.\ The next $m$ lines each contain an operation type, followed by the operation parameters. The formats are: 1. $\ l_x\ r_x\ v$ 2. $\ l_x\ r_x\ l_y\ r_y$

For each operation of type $2$, output one integer per line representing the answer.

### Sample Explanation The first four levels of the tree are shown in the figure:  Operation 1: Add $5$ to the weights of all nodes in the subtree rooted at $2$.\ Operation 2: Query the sum of weights on the path $2\rightarrow 10$.\ Operation 3: Add $3$ to the weights of all nodes in the subtree rooted at $2$.\ Operation 4: Query the sum of weights on the path $10\rightarrow 1$.\ Operation 5: Query the sum of weights on the path $1\rightarrow 2$. ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n\le$ | $m\le $ | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $10^3$ | $5$ | | $2$ | $20$ | $10^5$ | $5$ | | $3$ | $10^4$ | $10^4$ | $20$ | | $4$ | $4\times 10^5$ | $4\times 10^5$ | $70$ | For $100\%$ of the data, $1\le n,m\le 4\times 10^5$, $1\le v \le 10^9$, $1\le l_x\le r_x\le n$, $1\le l_y\le r_y\le n$, and it is guaranteed that $x,y\ne 0$. Translated by ChatGPT 5