题目思路

思路:树状数组模板题

转化题意之后，问题变为:给定一个序列，需要维护两类操作:单点修改值 + 区间查询和 . 这是经典的树状数组(BIT)的应用,简称裸题/模板题。我们可以做到$O(log\ n)$ 的修改和查询。

没有接触过的同学，塔子哥在此推荐以下几个学习网站:

1.B站视频-完全理解并深入应用树状数组

题目内容

小美是一个热爱收藏的年轻人，他喜欢收集各种有趣的物品，例如邮票、硬币、瓶盖等等。他的收藏品越来越多，于是他决定为自己在收藏架上建了一排 $n$ 个收藏夹，分别编号为 $1,2,3…n$。这样，他就可以更好地组织和展示自己的收藏品了。

小美有些时候会突发奇想改变某一个收藏美里的内容，例如从中拿入、拿出一些藏品，这些的操作会改变小美对这个收藏夹的欣赏程度，我们记编号为 $i$ 的收藏夹，小美对其的欣赏程度为 $a_i$ 。小美在休息时间经常会欣赏连续编号的收藏夹，例如编号为 $L,L+1,L+2,...,R-1,R$ 的这些收藏夹，他能从中获得的满足感为这些收藏失的欣赏程度之和，即 $\sum ^R _{i=L} a_i$ 。

小美想在欣赏之前提前估算自己能得到的满足感，想知道如果他选择编号区间为 $[L,R]$ 的收藏夹，能给他带来的满足感是多少。但是小美不想自己计算，所以他想你帮他计算一下，然后告诉他。

输入描述

第一行两个整数 $n$ 和 $m$ ，表示小美的收藏夹数量和小美的操作数量。初始时刻收藏夹都是空的，也即 $a_i = 0$ （ $i \in [1,n]$ ）

第二行 $m$ 个整数 $op_1,op_2,…,op_m$ 。

第三行 $m$ 个整数 $x_1,x_2,…,x_m$ 。

第四行 $m$ 个整数 $y_1,y_2,…,y_m$ ，这些共同表示了 $m$ 次操作，对于第 $i$ 次操作， $op_i=0$ 时表示为一次收藏夹更新操作，会将 $x_i$ 位置的收藏夹欣赏程度更新为 $y_i$ ，即 $a_{x_i} = y_i$ ； $op_i=1$ 时表示为一次查询操作，表示如果小美欣赏编号在区间 $[x_i,y_i]$ 的收藏夹，能获得的满足感是多少，也即 $\sum^{y_i}_{j=x_i} a_j$ 。

对于所有的数据， $1\le n,m \le 50000,op_i \in [0,1]$ ，当 $op_i = 0$ 时， $1\le x_i\le n,0\le y_i \le 10000$ ；当 $op_i = 1$ 时， $1\le x_i \le y_i \le n$ ，保证至少有一次 $op_i =1$ 的操作。

输出描述

对每一个 $op_i = 1$ 的操作，输出一个数表示对应答案。空格隔开所有答案。

样例

输入

4 7
1 0 1 0 1 0 1
1 1 1 3 1 4 1
3 2 3 5 3 100 3

输出

0 2 7 7

样例解释 操作记录为

0 0 0 0(初始)

询问[1,3]结果为0+0+0>

2 0 0 0<1号更改为2>

<询问[1,3],结果为2+0+0>

2 0 5 0 <3号更改为5>

<询问[1,3]结果为2+0+5>

2 0 5 100<4号更改为100>

<询问[1,3],结果为2+0+5>