410235: GYM103987 K Easy Homework

After data structure class in Sinoey's dream, Awson gave Sinoey a simple segment operation problem as his homework. Sinoey has $$$5$$$ hours to solve it before he wakes up.

There is a set $$$S$$$ containing all integers. Initially, the value of each element in $$$S$$$ is $$$0$$$. In this problem, Sinoey is given an integer sequence $$$a$$$ of length $$$n$$$, the $$$i$$$-th element of which is $$$a_i$$$, and he has to do the following two types of operations:

• R l r w. Let $$$T=\{a_i\mid l\le i\le r\}$$$. For each element $$$x$$$ in $$$T$$$, add $$$S_x$$$ by $$$w$$$. $$$(1\le l\le r\le n,\ |w|<2^{31})$$$
• A x. Output the value of $$$x$$$ in $$$S$$$. $$$(|x|<2^{31})$$$

The first line contains two integers $$$n\ (1\le n\le 10^5)$$$ and $$$q\ (1\le q\le 10^5)$$$, the length of sequence and the number of operations respectively.

The next line contains $$$n$$$ integers representing the sequence. For each element $$$a_i$$$ in the sequence, $$$|a_i|<2^{31}$$$ is guaranteed.

Each of the next $$$q$$$ lines indicates an operation. The formats and constraints are introduced above.

For each query, print the answer in a line.

The problem contains several subtasks. You can get the corresponding score only if you have passed all test cases in a subtask.

• Subtask 1 ($$$20$$$ points): $$$n\le 100$$$.
• Subtask 2 ($$$80$$$ points): no additional constraints.

4 5
1 2 1 3
R 1 3 1
A 1
R 2 4 1
A 1
A 3

1
2
1

The interval in the first operation contains two different elements: $$$1$$$ and $$$2$$$, so $$$S_1$$$ and $$$S_2$$$ will increase by one after the first operation.