Help me to solve this problem

Revision en2, by kritipandey, 2021-06-23 13:06:07
  • 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
Tags prefix sum

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kritipandey 2021-06-23 15:30:29 26
en4 English kritipandey 2021-06-23 14:11:27 61
en3 English kritipandey 2021-06-23 13:55:29 69
en2 English kritipandey 2021-06-23 13:06:07 36
en1 English kritipandey 2021-06-23 13:04:01 1079 Initial revision (published)