Hacker with Team

Practice

4.5 (8 votes)

Approved

Data structures

Easy

Fenwick tree

Problem

28% Success 6283 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Alex has learnt many new concepts in hacking, and created his own team. He has N people (excluding Alex) in his team, where \(i^{th}\) person has individual skill value \(S_i\) where \(1 \le i \le N\). They are standing in a particular order, where \(1^{st}\) person being the leftmost person and \(N^{th}\) person being the rightmost person. Alex has found a special way to evaluate the contribution done by each person in the team. Contribution done by \(i^{th}\) person (\(C_i\) ) in the team can be calculated as sum of his skill value and the skill values of his K adjacent team members on the left side, where the value of K will be decided by Alex. In case, there are not enough members on the left side, contribution will be equal to the sum of his skill value and the skill values of all the team members on the left side. Alternatively, \(\space\space\space\space\space\) \(C_i\) = \(\sum_{j = maximum(i-K,1)}^{i } S_j\) Alex can perform 2 types of operations now: 1) He can write a program to calculate the total contribution done by all the team members in the range of l to r (both inclusive), where contribution of each person will be calculated using value of K decided by him. 2) He can ask any person to change his skill value to X. Being a great hacker, he is busy with other tasks, and needs your help in performing above operations. Input Format: First line contains 2 space-separated integers N and Q, where N denotes the number of people in Alex's team and Q denotes the number of operations Alex wants to get completed. Second line contains N space-separated integers, where \(i^{th}\) integer denotes the skill value of \(i^{th}\) person in the team. In next Q lines, each line contains first integer O, which represents the type of operation. \(\space\) 1) For \(O=1\), line will contain 3 more space-separated integers \(l,r\) and K. Here Alex wants to know the total contribution done by all team members in the range l to r (both inclusive), where contribution of each person will be calculated using value of K decided by him. \(\space\) 2) For \(O=2\), line will contain 2 more space-separated integers i and X where Alex asks \(i^{th}\) person to change his skill value to X. Output Format: For each operation of the \(1^{st}\) type, print the required answer in the new line. Constraints: \(1 \le N,Q \le 10^5\) \(1 \le S_i, X \le 10^8\) \( 1 \le l \le r \le N\) \( 1 \le K \le N\)

Sample Input

6 3
1 2 3 4 5 6
1 4 5 2
2 4 3
1 4 5 2

Sample Output

21
19

Explanation

Here \(N = 6\), and \(Q = 3\). For first operation \(O=1\) and \(l = 4\) , \(r = 5\) and \(K= 2\). It means, we need to evaluate the contribution done by all the team members in the range \([4,5]\) with \(K=2\). Therefore: \(C_4 = S_4 + S_3 + S_2 = 4 + 3 + 2 = 9 \) \(C_5 = S_5 + S_4 + S_3 = 5 + 4 + 3 = 12 \) So total contribution is \(21\). For second operation \(O=2\), i.e \(4^{th}\) person will change his skill to 3, i.e \(S_4 = 3\). For third operation, \(O=1\) and \(l = 4\) , \(r = 5\) and \(K= 2\). Now the required contribution will be \(19\).

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions