Chef and Queries Codechef Solution

by

Chef and Queries Solution Problem Code: CHEFQUER

You are given a sequence A1,A2,…,ANA1,A2,…,AN. Chef wants you to handle QQ queries. There are two types of queries:

  • 1 L R X: for each ii (L≤i≤RL≤i≤R), add (X+i−L)2(X+i−L)2 to AiAi
  • 2 Y: find the current value of AYAY

Input

  • The first line of the input contains two space-separated integers NN and QQ.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
  • QQ lines follow. Each of these lines describes a query in the format described above.

Output

For each query of the second type, print a single line containing one integer AYAY.

Constraints

  • 1≤N,Q≤1051≤N,Q≤105
  • 0≤|Ai|≤1060≤|Ai|≤106 for each valid ii
  • 1≤L≤R≤N1≤L≤R≤N
  • 0≤|X|≤1060≤|X|≤106
  • 1≤Y≤N1≤Y≤N

Example Input

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

Example Output

52
69

Explanation

  • the sequence after the first query is [1+52,10+(5+2−1)2,3+(5+3−1)2,6,5]=[26,46,52,6,5][1+52,10+(5+2−1)2,3+(5+3−1)2,6,5]=[26,46,52,6,5]
  • the second query asks for A3A3, which is 5252
  • the sequence after the third query is [26,46,52,6+72,5+(7+1)2]=[26,46,52,55,69][26,46,52,6+72,5+(7+1)2]=[26,46,52,55,69]
  • the fourth query asks for A5A5, which is 69

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

nineteen + 11 =