Module: 根分解


Problem

3 /6


段总和 - 2

Theory Click to read/hide

我们有一个问题，关于如何快速计算数组 a 中的段 l...r 的总和，其中的元素一次可以改变一个，渐近小于 O(n)。
这个任务的解决方式与上一个任务类似，但是在请求更改时，需要更改相应块中的金额。

Problem

给定一个长度为 n 的数组 a (\(1 <= n <= 2 \cdot 10^6\ ), \(1 <= a_i <= 10^9\))。还给出了 m (\(1 <= m <= 500\)) 查询，如 t， l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

如果 \(t = 0\)，则查询应显示来自 l 到 r 包括在内。如果 \(t = 1\)，则元素编号 l 设置为 r。 元素是编号从 1 到 n。 

 

例子
<头> <日># <正文>

time 3000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

输入 输出
1
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
 3
7
5