 # COWA19B-Editorial

COWA19B (Pongal Bunk)

concept related: prefix array sum

Approach:-

Maintain two arrays (array1,array2).
-> first array (array1) to know the number of queries having the specific index in their range of L,R. For each query apply,

``````1)array1[L]=array1[L]+1
2) array1[R+1]=array1[R+1]-1
``````

->second array (array2) to know the final value of element in the specific index of array for each query to apply,

`1) array2[R+1]=array2[L]-(R-L+1)`

After Performing All the queries operations,

->Run an iteration for prefix array sum for array1 i.e ,
`array1[i]=array[i]+array1[i-1] (where 1<=i<=N)`

->Run other iteration for array2 similar to prefix sum doing following operations
`array2[i]=array2[i] + array2[i-1] + array1[i] (where 1<=i<=N)`

Now, array2 contains the final values of elements present in array

Time-complexity: O(n+q+m)

reference-code for the problem is given below-

``````#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;

int main()
{
ll ans,ans1;
memset(ans1,0,sizeof(ans1));
memset(ans,0,sizeof(ans));
ll n,q,l,r;
cin>>n>>q;
while(q--)
{
cin>>l>>r;
ans[l]+=1;ans[r+1]-=1;
ans1[r+1]-=(r-l+1);
}
for(int i=1;i<=n;i++)
ans[i]+=ans[i-1];
for(int i=1;i<=n;i++)
ans1[i]+=ans1[i-1]+ans[i];
cin>>q;
while(q--)
{
cin>>l;
cout<<ans1[l]<<endl;
}
}
``````