### kritipandey's blog

By kritipandey, history, 5 weeks ago, • You are given an array A of size N. Initially all the elements of the array are zero. Also, you have an infinite length array S which holds the property that the index is equal to the value of the array i.e. for each i(i>=1),S[i]=i.
• Now you have Q queries to perform on array A. Each query contains two variables L and R.
• For each query you have to perform the following operations:
• For all index i, where L<=i<=R you have to add the value of the array S from starting position incrementing its positions to the array element at index i. That is:
• initialize j=1;
• for each i=L to R:
• A[i]=A[i]+S[j]
• j=j+1
• After performing Q queries, you need to output the final values present in array A
• INPUT FORMAT:
• First line contains integer N indicating the size of the array indexed from 1 to N.
• Second line contains integer Q indicating no of Queries.
• Followed by Queries where each line contains two no L and R.
• 1<=N<=100000
• 1<=Q<=100000
• 1<=L<=R<=N
• Output Format:
• Print output of final values present in array A in a space separated order  Comments (16)
 » Auto comment: topic has been updated by kritipandey (previous revision, new revision, compare).
 » Please provide the link to the question. Otherwise how can it be checked if it is from a ongoing test.
•  » » Its from walmart or lowes test that has ended and is not from any ongoing test
 » Auto comment: topic has been updated by kritipandey (previous revision, new revision, compare).
 » Auto comment: topic has been updated by kritipandey (previous revision, new revision, compare).
 » Create a new array $C$, for each query $(L, R)$, add $1$ to $C[L]$, add $L-R-2$ to $C[R+1]$ and $R-L+1$ to $C[R+2]$. At the end $A=prefixsum(prefixsum(C))$