P10045 [CCPC 2023 Beijing Municipal Contest] Segment Tree

There is a sequence $a_1,a_2,\cdots,a_n$ of length $n$, and it is guaranteed that $a_i$ is **odd**. There are two types of operations: 1. Given $l, r, x$, add the **even** number $x$ to $a_l,a_{l+1},\cdots,a_r$. 2. Given $l, r$, compute the product of $a_l,a_{l+1},\cdots,a_r$, and take the answer modulo $2^{20}$.

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries. It is guaranteed that $1 \le n, q \le 2 \times 10^5$. The second line contains $n$ **odd** integers $a_1,a_2,\cdots,a_n$. It is guaranteed that $1 \le a_i < 2^{20}$. The next $q$ lines each describe one operation, in one of the following two formats: - $1 ~ l ~ r ~ x$: perform the first operation. It is guaranteed that $1 \le l \le r \le n$, $0 \le x < 2^{20}$. - $2 ~ l ~ r$: perform the second operation. It is guaranteed that $1 \le l \le r \le n$.

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

Translated by ChatGPT 5