仓鼠的执念

题目描述

仓鼠在2023年ACM-ICPC国际大学生程序设计竞赛亚洲区域赛-沈阳站中，Problem K主要考察了这样的一个问题: 维护一个序列，每次操作可以修改序列中的一个值为另一个值，或者查询全局中前k大数的和。 由于仓鼠当时对数据结构的理解不够深刻，进而最后也没能通过此题，从而与铜牌失之交臂。仓鼠对此执念颇深，因此在之后督促Orange加训数据结构时，每次都会让Orange给出本题的做法。在Orange加训数据结构之后，他认为之前的问题过于简单，因此他将题目的全局前k大和改成了区间前k大和，请你完成这个数据结构。

换句话说，题目会给定一个长度为 $n$ 的序列 $a$，你需要支持如下两种操作:

1. 每次给定一个位置 $i$; 修改 $a_i$ 为 $x$。
2. 每次给定一个区间 $[l,r]$ 和一个整数 $k$，查询区间所有数从大到小排序后，前 $k$ 个数的和是多少。

输入格式

第一行为一个整数 $n(n \leq 2 \times 10^5)$，表示序列长度。

第二行为一个长度为 $n$ 的整数序列 $a_i(a_i \leq 10^9)$。

第三行为一个整数 $q(q \leq 2 \times 10^5)$，表示操作次数。接下来的每一行表示一个操作，首先第一个数 $op$ 表示操作编号，如果是操作 $1$，那么后面会跟两个整数 $pos$ 和 $x(1 \le pos \le n; x \le 10^9)$，表示将位置为 $pos$ 的数修改成 $x$；如果是操作 $2$，那么后面会跟三个整数 $l,r,k(1 \le l \le r \le n; \ k \le r-l+1)$，表示查询的区间和 $k$。

输出格式

对于每个查询，输出一个答案。

样例 #1

样例输入 #1

5
3 2 1 4 7
3
2 1 4 3
1 2 6
2 2 5 3

样例输出 #1

9
17

提示

#样例解释:

对于第一个查询，序列区间为[1;4]即为3 2 1 4;其从大到小排序后为4 3 2 1;前3大的数是4 3 2;因此答案为4 + 3 + 2 = 9。