P5303. 拍品价差总和

场次：2026年8月25日 · 来源：CodeFun2000 P5303

题目描述

夜场拍卖同时挂出 k 件拍品。每件拍品当前有一个整数出价，记成数组 $v_1,v_2,\ldots,v_k$。值班估价员要盯的不是单件高低，而是当前全部拍品两两出价的绝对差之和，用来衡量这一轮报价有多散。场刊规定：可以把某一件拍品的出价改成新值，也可以随时查询当前的价差总和。

对当前出价数组 $v$，价差总和定义为所有无序对的绝对差之和。也就是先枚举所有下标对 $(p,q)$（满足 $1\le p<q\le k$），再把 $|v_p-v_q|$ 加起来：

$$W(v)=|v_1-v_2|+|v_1-v_3|+\cdots+|v_{k-1}-v_k|.$$

共有两类指令（指令编号必须是 1 或 2）：

1. 1 $p$ $y$：把 $v_p$ 改成 $y$。
2. 2：查询当前的 $W(v)$。

第一行一个整数 $G$，表示后面有多少段互不相关的场次记录。对每一段单独维护拍品出价，并按出现顺序输出该段内每一次查询的结果。全部场次的 $(k+q)$ 之和不超过 500000。

其余约束：1 $\le$ $G$ $\le$ 100000，单段 1 $\le$ $k,q$ $\le$ 200000，出价与修改值的绝对值不超过 1000000000。

输入格式

第一行一个整数 $G$（1 $\le$ $G$ $\le$ 100000）。

每一段记录格式如下：

第一行两个整数 $k,q$（1 $\le$ $k,q$ $\le$ 200000）。

第二行 $k$ 个整数 $v_1,v_2,\ldots,v_k$（绝对值不超过 1000000000）。

接下来 $q$ 行，每行一条指令：修改为 1 $p$ $y$（1 $\le$ $p$ $\le$ $k$，绝对值不超过 1000000000）；查询为单独一个 2。

保证全部记录中 $k+q$ 的总和不超过 500000。

输出格式

对每条查询指令输出一行一个整数，即当前的 $W(v)$。

示例

示例 1

输入：

1
3 4
0 5 2
2
1 3 9
2
1 1 5
2

输出：

10
18
8

说明：

初始出价为 0、5、2：

• $|0-5|+|0-2|+|5-2|=10$。

把第 3 件改成 9，变成 0、5、9：

• $|0-5|+|0-9|+|5-9|=18$。

把第 1 件改成 5，变成 5、5、9：

• $|5-5|+|5-9|+|5-9|=8$。

示例 2

输入：

1
2 2
7 7
2
1 2 3
2

输出：

0
4

说明：

两件拍品出价相同，绝对差为 0。把第二件改成 3 后，$|7-3|=4$。