balance

Kircho has an array of $N$ integers (not necessarily non-negative) — $a_0, a_1, ... a_{N-2}, a_{N-1}$. He can perform operations on the array. Each operation is characterized by a pair $(l,r)$ such that $0 \leq l \leq r < N$, and for this operation he can choose to perform exactly one of the following two actions:

• for every $x \in \{0, 1, ..., r-l-1, r-l\}$, add $(-1)^x$ to $a_{l+x}$;
• for every $x \in \{0, 1, ..., r-l-1, r-l\}$, subtract $(-1)^x$ from $a_{l+x}$.

Let the balance of an array be defined as the minimum number of operations required to make all its elements equal to zero. Kircho wants to determine the balance of several arrays, each of which is a subarray of the main array. However, between queries the array may change via updates to individual elements. For more information about updates, see the Implementation details section. Unfortunately, Kircho cannot answer the queries himself, so he asks you to write a program balance that solves the problem.

An array $p$ is a subarray of an array $q$ if $p$ can be obtained from $q$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Implementation details

This is an interactive problem, which means that information between your program and the jury program will not be exchanged through standard input and output, but through special functions.

You must implement the following functions:

void init(const std::vector<int>& A);

This function is called exactly once at the beginning of each test. The vector $A$ contains $N$ integers - $a_0, a_1, ..., a_{N-1}$, representing the initial array.

long long balance(int u, int v);

This function represents a query for the balance of the subarray $a_u, a_{u+1}, ..., a_{v-1}, a_v$. The function must return the balance of the subarray. All calls to balance() are independent of each other.

void update(int p, int x);

This function represents an update to the array — it sets $a_p$ to $x$. This change applies to all subsequent function calls within the current test.

You must submit a file balance.cpp, which contains the functions init(), balance(), and update(). It may also contain other code and helper functions necessary for your program, but it must not contain the main function main(). At the beginning, your file must include:

#include "balance.h"

Your program will be executed once for each test.

Constraints and clarifications

• Let $Q$ be the total number of calls to the functions balance() and update() within a test.
• $1 \leq N,Q \leq 10^5$
• $-10^9 \leq a_i,x \leq 10^9$
• $0 \leq u_i \leq v_i < N$
• $0 \leq p_i < N$
• It is guaranteed that there is at least one call to balance()
• An alternating array is defined as one in which all numbers are nonzero and their signs alternate.

Sample interaction

Explanation

In this example, the initial array is $a = (3, −4, 2, −4, 3)$. For the first query, Kircho can perform the following sequence of operations:

For the second query:

After the update, the array becomes $a = (2, −4, 2, −4, 3)$, and Kircho can perform:

It can be proven that these sequences of operations are optimal.

Local testing

You are given the files balance.h and Lgrader.cpp, which you can compile together with your program to test it locally, along with compilation commands.

When running the local grader, on the first line of standard input you must enter the positive integers $N$ and $Q$. On the second line, enter $N$ integers — $a_0, ..., a_{N-1}$ — representing the initial array. Each of the next $Q$ lines describes either a query or an update. At this point, the grader will call init() with parameter $A = \{a_0, ..., a_{N-1}\}$. At the beginning of each query, enter an integer $t_i$ , where $1 \leq t_i \leq 2$. If $t_i = 1$, then enter two integers $u_i$ and $v_i$, representing a call to balance() with parameters $u_i$ and $v_i$. If $t_i = 2$, then enter two integers $p_i$ and $x_i$, representing a call to update() with parameters $p_i$ and $x_i$.

For each call to balance(), the local grader will output the returned value. The order of function calls follows the input.