问题 C: Clamped Sequence II

链接：https://ac.nowcoder.com/acm/contest/57362/C
来源：牛客网
For an integer sequence a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an and a positive integer $d$, the $d$-clamped value of the sequence is the maximum value of ∑i=1n−1∑j=i+1n∣ai−aj∣\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}|a_i - a_j|∑i=1n−1∑j=i+1n∣ai−aj∣, where $|x|$ is the absolute value of $x$, after appointing a range [l,r][l,r][l,r] satisfying 0≤r−l≤d0 \le r-l \le d0≤r−l≤d and clamping the sequence to the range [l,r][l, r][l,r].

More specifically, clamping the sequence to the range [l,r][l,r][l,r] makes each element


Both $l$ and $r$ are arbitrary real numbers decided by you under the given constraints. It can be shown that the maximum sum is always an integer.

Now, given an integer sequence a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an and $q$ queries, where each query is in one of the two following formats:

• $1$ $x$ $d$  denotes setting axa_xax to $d$
• $2$ $d$ denotes reporting the d-clamped value of the current sequence

Please output the answer for each reporting queries.

The first line contains two integers $n$ (2≤n≤1052\le n\le 10^52≤n≤105) and $q$ (1≤q≤1051\le q\le 10^51≤q≤105), denoting the length of the given sequence and the number of queries.
The second line contains $n$ integers a1,a2,…,ana_1, a_2, \ldots, a_na1,a2,…,an (1≤ai≤1061 \le a_i \le 10^61≤ai≤106), denoting the given sequence.
Each of the following $q$ lines contains a query, which is in one of the two following formats:
$1$ $x$ $d$  ($1\le x\le n$, 1≤d≤1061 \le d \le 10^61≤d≤106) denotes setting axa_xax to $d$
$2$ $d$  (1≤d≤1061 \le d \le 10^61≤d≤106) denotes reporting the $d$-clamped value of current sequence

For each reporting query, output one line containing a single integer, denoting the $d$-clamped value of the current sequence.

8 3
3 1 4 1 5 9 2 6
2 3
1 2 8
2 4

46
58