[R2F]带修求和 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定一个长度为 $n$ 的正整数数组 $A$ 以及 $q$ 个操作，操作分为以下三种：

$1\ x\ y$：表示将序列第 $x$ 项 $A_x$ 的值改为 $y$。

$2\ v$：表示询问最少几项 $A_i$ 相加，使得和大于等于 $v$。

$3\ v$：表示询问最多几项 $A_i$ 相加，使得和小于等于 $v$。

格式

输入格式

第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个正整数，表示数组 $A$ 的初始值。

第三行包含一个整数 $q$，表示操作的数量。

接下来 $q$ 行每行一个操作，格式见题目描述。

输出格式

对于每个 $2$ 或 $3$ 类的询问，在单独的一行中输出一个整数表示答案。无解输出 $\text{-1}$。

样例

样例输入 #1

5
1 2 3 4 5
9
2 6
1 5 2
2 6
1 4 2
2 6
1 1 4
3 1
2 14
2 0

样例输出 #1

2
2
3
0
-1
0

数据规模

对于 $100\%$ 的数据， $1\leq n,q\leq 5\times 10^5$， $1\leq x\leq n$， $1\leq A_i,y\leq 5\times 10^6$， $0\leq v\leq 10^{18}$。

测试点编号	$n,q$	$A_i,y$	特殊性质
1	$\leq 500$	$\leq 10^5$	$\text{无}$
2	$\leq 10^5$	$\leq 50$
3~4		$\leq 10^5$	$\text{没有类型 1 的操作}$
5~8			$\text{无}$
9~10	$\leq 5\times 10^5$	$\leq 5\times 10^6$