本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1149. 区间修改,单点查询


Description

给定数列a[1], a[2], ... , a[n] ,你需要依次进行 q  个操作,操作有两类:

  • 1 l r x:给定 l,r,x,对于所有 i \in [l,r],将 a[i] 加上 x(换言之,将 a[l], a[l+1],...,a[r] 分别加上 x);
  • 2 i:给定 i ,求 a[i] 的值。

Input

第一行包含 2 个正整数 n,q,表示数列长度和询问个数。保证1<=n,q<=106
第二行  n 个整数 a[1], a[2],..., a[n],表示初始数列。保证|a[i]|<=106
接下来 q 行,每行一个操作,为以下两种之一:

  • 1 l r x:对于所有  i \in [l,r],将 a[i] 加上 x
  • 2 i:给定 i,求 a[i]  的值。

保证 1<=l<=r<=106, |x|<=106

Output

对于每个 2 i 操作,输出一行,每行有一个整数,表示所求的结果。

Samples

Input Copy
3 2
1 2 3
1 1 3 0
2 2
Output
2

Hint

对于所有数据,1<=n,q<=106 , |a[i]|<=106, 1<=l<=r<=n, |x|<=106  

Source

树状数组 loj131
Problem Information

Time Limit: 3000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 6 / 17
Tags:
Contests involved

1018. 树状数组--loj.ac
My history solutions

You didn't submit any solution!
Submit your solution

Login Register