题解

题面描述

给定一个长度为 $n$ 的数组 $a$，需要支持两种操作：

• 修改操作：给定数字 $v$，将数组中每个元素更新为 $\min(a_i, v)$。也就是说，对于所有 $1 \le i \le n$，令$$a_i := \min(a_i, v).$$

题目内容

小苯有一个长度为$n$的数组$a$，他希望你在$a$上维护两种操作，具体来说：

• 修改:他每次给出一个数字$v$，表示$a$中所有的数字和$v$取较小者。形式化的:对于$i(1≤i≤n)$,执行$a_i=min(a,v)$。

• 查询:查询数组中所有数字的和是多少。

  他觉得这个问题过于困难，请你帮他处理一下这些操作吧。

输入描述

本题有多组测试数据。

输入的第一行包含一个正整数

$(1≤T≤100)$,表示数据组数。

接下来包含$T$组数据，每组数据的格式如下:

第一行两个正整数$n,q(1≤n,q≤2×10^5)$，分别表示数组$a$的长度和操作的次数。

第二行$n$个正整数$a_i (1≤a_i≤10^9)$，表示数组$a$。

接下来$q$行，每行一个操作，输入格式为:

• $1.v$表示修改操作($1≤v≤10^9)$
• $2$.表示查询操作。

(保证所有测试数据中，$n,q$的总和都不超过$2×10^5$)

输出描述

对于每组数据，每行输出一个整数，表示满足条件的数字个数。

样例1

输入

1
5 3
1 2 4 5 3
2 
1 2
2

输出

15
9

说明

首先查询数组的总和为:$1+2+4+5+3=15$

接着我们进行一次操作，将所有元素和$v=2$取$min$，数组变为:{$1,2,2,2,2$}。

再次查询数组的总和为:$1+2+2+2+2=9$