分块模板1

分块模板1

题目描述

给出一个长为nn的数列,有tt次操作.

opop=1对应区间同加一个数,opop=0表示查询一个点xx的权值.

输入

第一行包含两个数nn,tt,表示原始数组的元素个数和操作的个数。

第二行包括nn个数,表示原始数组。

以下tt行,每行格式为11 ll rr xx或者00 xx,其中第一个数为1表示加入操作,为0表示询问操作。

输出

对每个询问操作输出一行,包括一个数,表示该点的值。

样例输入

10 4 
1 5 2 6 7 4 9 3 1 5 
1 1 1 1
0 1
1 2 3 4
0 2

样例输出

2
9

提示

33%的数据满足1<=n1<=n, m<=2000m<=2000,删除操作不超过20002000
66%的数据满足1<=n1<=n, m<=10000m<=10000, 1<=t<=100001<=t<=10000
100%的数据满足1<=n1<=n, m<=200000m<=200000, 1<=m<=2000001<=m<=200000
对于所有的数据,数组中的元素绝对值均不超过nn

信息

难度
9
分类
分块数据结构 点击显示
标签
递交数
4
已通过
1
通过率
25%
上传者