COWA19B-Editorial

COWA19B (Pongal Bunk)

PROBLEM LINK:

Practice
Contest

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[1000002],ans1[1000002];
    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;
    }
} 

some-useful-links:-


1 Like

@himkha_100
You have explained about how your solution works!
But could you also explain the intution behind how you came up with this solution!?

14 Likes

Great editorial… Thanks!

@kishore_7298
bro first array is used for keeping a record of the value by which we need to update with index usage i.e. 1 and the second array is used for updation by adding index…
its kinda like using 2 difference arrays for solving but i didn’t got the intution for it either :slight_smile:

we can solve this problem by using two array and store the final answer in the third array

1.one for taking the l and r so that we can find out which no is repeated in between l and r;
  we can do that by taking
                           arr[l]=arr[l]+1;
                           arr[r+1]=arr[r=1]-1;
                           by doing this and then taking the prefix sum array of this 
                           array we will going to get the 
                           array which is going to tell the no of times a given element is 
                           repeated in the q query between l and r
                           and by doing so we are going to get  
                           2 3 3 2 1  //this gives the no of occurrence 

2.in the second array we can understand it by using the given example 
        starting array     0 0 0 0 0
    after first query      1 2 3 
    after second query       1 2 3 
    after third query      1 2 3 4 5

    so the final sum       2 5 8 7 5

    so we can observe that it doesn't matter the l is anything the no which is 
    shown in the array for any l and r is  1 2 .. r 
    so we want the second array such that it will somehow give us the normal 
    value(1 2 3.. r) independent of l starting from l to r
    we can do that by arr2[l]=arr2[l]-l;       
                      arr2[r+1]=arr2[r+1]+l;
                      and then take the prefix sum of the following array
                       so we get            0 -1 0 0 1 0
                  after prefix sum          0 -1 -1 -1 0 0

3.And for the final array we are going to add the arr2 to the number of 
   times the no is occoured by array1 to thier respective index+1
        ie sol[i]=arr2[i]+(i+1)*arr1[i];

This solution is giving TLE

1 Like

i have made a video for this editorial hope its helps

3 Likes

We can do it using a single array as well just add r-l+1 at the (r+2)th position and subtract (r-l+2) from (r+1)th position and add 1 at the l th position and take the prefix sum 2 times.
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
int n;
cin>>n;

vector<int> v(n+1,0);

int q;
cin>>q;
int l, r;
while(q--)
{
    cin>>l>>r;
    v[l]+=1;
    if(r+1<n+1)  v[r+1]-= (r-l+2);
    if(r+2<n+1)  v[r+2]+=(r-l+1);


}
// two times pre sum
for(int i=2;i<n+1;i++)
{

    v[i]+=v[i-1];
}
 for(int i=2;i<n+1;i++)
{

    v[i]+=v[i-1];
}

int m;
cin>>m;

int a;
while(m--)
{
    cin>>a;
    cout<<v[a]<<endl;
}

}

can anyone explain for what work we are using the second array

How to solve a problem, which has values in an array not like this problem which zero only , and we are adding variable range sum to the values , how to apply scandline algo to these kind of problem.
For eg this type of problem.
https://www.codechef.com/START5C/problems/CHEFQUER