19505번 - Process with Constant Sum 다국어

Suppose we have an array $a$ whose elements are non-negative integers. We can apply operations of two types to this array:

1. $a_{i} \gets a_{i} - 2$, $a_{i+1} \gets a_{i+1} + 2$.
2. If $a_{i+1} = 0$: $a_{i} \gets a_{i} - 1$, $a_{i+2} \gets a_{i+2} + 1$.

After any operation, all the elements must remain non-negative.

It is easy to see that we cannot do such operations indefinitely. We'll call a chain of operations maximal if no valid operation can occur after performing this chain of operations.

Now you are given an array $b$ of length $n$. Your should handle two types of queries:

• "1 $p$ $x$" --- assignment $b_{p} \gets x$.
• "2 $l$ $r$" --- let us treat the subsegment $b[l..r]$ as array $a$. You have to find the maximum number of zeroes which can be in that array after applying some maximal chain of operations. Note that we don't really change the array $b$ during this query.

The first line of input contains one integer $n$, the length of array $b$ ($1 \le n \le 2 \cdot 10^{5}$).

The second line contains $n$ integers separated by spaces: the initial elements of array $b$ ($0 \le b_{i} \le 10^{5}$).

The third line contains one integer $q$, the number of queries ($1 \le q \le 2 \cdot 10^{5}$).

Each of the next $q$ lines contains a query.

For queries of the first type, $1 \le p \le n$ and $0 \le x \le 10^{5}$.

For queries of the second type, $1 \le l \le r \le n$.

For each query of the second type, print the answer on a separate line. Answers should be printed in the same order as queries.