P12179 DerrickLo's Game (UBC002B)

There is an array $a$ with $n$ numbers ($1\le n,a_i\le 2\times10^5$). You have to handle $q$ modifications or queries ($1\le q\le 2\times10^5$). There are two types of modifications or queries: - Input `1 k x`, this changes $a_k$ into $x$ ($1\le k\le n$, $1\le x\le 2\times10^5$) (modify). - Input `2 l r`, you have to print the minimum cost of making $a_l\dots a_r$ the same by the two operations below (**This does not really changes the array.**) ($1\le l\le r\le 2\times 10^5$) (query): 1. Choose an integer $p$, increase $a_p$ by $1$. This costs $1$. 2. Choose an interval $[x,y]$, change $a_x\dots a_y$ into $\max\limits_{i=x}^ya_i$. This costs $(y-x+1)^2$.

The first line contains two integers $n,q$. The second line contains $n$ integers, representing $a$. For the next $q$ lines, each line contains three integers, representing a modify or a query.

Suppose there are $t$ queries. Please output $t$ lines, representing the answers for each one.

For the first query, we choose $a_1$ and increase it by $1$. This costs $1$. So output $1$. For the second query, we don't need to do any operations since the number in $[1,1]$ is already the same.