← 返回题目列表

Codeforces · 1791/F

F. 范围更新点查询

中文机器翻译题面 查看原题

给定一个数组 $$$a_1, a_2, \dots, a_n$$$,您需要处理总共 $$$q$$$ 更新和两种类型的查询:

- $$$1$$$ $$$l$$$ $$$r$$$ - 对于 $$$l \leq i \leq r$$$ 的每个索引 $$$i$$$,将 $$$a_i$$$ 的值更新为 $$$a_i$$$ 的数字总和。
- $$$2$$$ $$$x$$$ —输出$$$a_x$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 分别是数组的大小和查询的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

每个测试用例接下来的 $$$q$$$ 行有两种形式:

- $$$1$$$ $$$l$$$ $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) - 这意味着,对于每个带有 $$$l \leq i \leq r$$$ 的索引 $$$i$$$,您应该将 $$$a_i$$$ 的值更新为其数字之和。
- $$$2$$$ $$$x$$$ ($$$1 \leq x \leq n$$$) - 这意味着你应该输出 $$$a_x$$$。

至少有一个第二类型的查询。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,按照给出的顺序输出第二类型查询的答案。

示例

输入 #1

3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1

输出 #1

6
15
1434
1
6
7
36
1
1

注意

在第一个测试用例中,发生以下过程:

- 最初,$$$a = [1, 420, 69, 1434, 2023]$$$。
- 对 $$$l=2$$$、$$$r=3$$$ 执行该操作,产生 $$$[1, \color{red}{6}, \color{red}{15}, 1434, 2023]$$$。
- 我们查询 $$$x=2$$$、$$$x=3$$$ 和 $$$x=4$$$,并输出 $$$6$$$、$$$15$$$ 和 $$$1434$$$。
- 对 $$$l=2$$$、$$$r=5$$$ 执行该操作,产生 $$$[1、\color{red}{6}、\color{red}{6}、\color{red}{12}、\color{red}{7}]$$$。
- 我们查询 $$$x=1$$$、$$$x=3$$$ 和 $$$x=5$$$,并输出 $$$1$$$、$$$6$$$ 和 $$$7$$$。