问题 C: Clamped Sequence II
内存限制:512 MB
时间限制:5.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
For an integer sequence a1, a2, . . . , an and a positive integer d, the d-clamped value of the sequence is the
maximum value of Pn−1
i=1
Pn
j=i+1 |ai − aj |, where |x| is the absolute value of x, after appointing a range
[l, r] satisfying 0 ≤ r − l ≤ d and clamping the sequence to the range [l, r].
More specifically, clamping the sequence to the range [l, r] makes each element
ai
:=
l, ai < l;
ai
, l ≤ ai ≤ r;
r, ai > r.
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, . . . , an and q queries, where each query is in one of the two following
formats:
• 1 x d denotes setting ax 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 ≤ 105
) and q (1 ≤ q ≤ 105
), denoting the length of the given
sequence and the number of queries.
The second line contains n integers a1, a2, . . . , an (1 ≤ 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 ≤ x ≤ n, 1 ≤ d ≤ 106
) denotes setting ax to d
• 2 d (1 ≤ 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