P17738 [ICPC 2019 Xuzhou R] Yuuki and a problem

Yuuki, a cute senior high school student with excellent talent in mahjong, comes up with a cool problem. The problem goes as follows: Given a sequence with $N$ integers $a_1, a_2, \cdots, a_N$ and $Q$ operations. There are two types of operations. - Modify operation: Given $x, y$, change $a_x$ to $y$. - Query operation: Given $L, R$. Consider $a_L, a_{L + 1}, \cdots, a_{R}$ as coins with values $a_L, a_{L + 1}, \cdots, a_R$, please find out the minimum number $yuuki$, such that it is impossible to choose a subset of the coins stated before, such that the sum of their values is $yuuki$.

The first line of the input contains two integers $N, Q$ denotes the length of the sequence and the number of operations. Then, there are $N$ space-separated integers $a_1, a_2, \cdots, a_N$. Then, the following $Q$ lines are the operations. Each operation must follow the following two formats: 1. $1 \ x \ y$: Modify operation. 2. $2 \ L \ R$: Query operation. The meaning of the variable are stated in the problem description! - $1 \le N, Q, a_i \le 2 \times 10^5$ - $1 \le x \le N$ - $1 \le y \le 2 \times 10^5$ - $1 \le L \le R \le N$

For each query operation, output the corresponding $yuuki$ value in one line.