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:-

2 Likes

@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!?

15 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];
1 Like

This solution is giving TLE

2 Likes

i have made a video for this editorial hope its helps

4 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.

1) array2[R+1]=array2[L]-(R-L+1)
There is a correction here : array2[R+1] = array2[R + 1]-(R-L+1)

this approach is easy and thinkable intrusion is so simple take two array one to keep track of no of queries applied on index and one too keep track of index.

int n;cin>>n;
int a[n+1]={0};int b[n+1]={0};

int q;
cin>>q;
for (int i = 1; i <=q; i++) {
    int l,r;
    cin>>l>>r;
    b[l]+=l;b[r+1]-=l;
    a[l]++;a[r+1]-=1;
}


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

for (int i = 1; i <=n; i++) {
    a[i]=a[i]*i-b[i]+a[i];
}

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

}

My intuitive solution


#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int n;
	scanf("%d",&n);
	int a[n],b[n];
	for(int i=0;i<n;i++){a[i]=0;b[i]=0;}
	int q;
	scanf("%d",&q);
	while(q--)
	{
	    int l,r;
	    scanf("%d %d",&l,&r);
	    a[l-1]++;
	    if(r!=n)
	    a[r]--;
	    b[l-1]+=l;
	    if(r!=n)
	    b[r]-=l;
	}
	for(int i=1;i<n;i++)
	    {
	        a[i]+=a[i-1];
	        b[i]+=b[i-1];
        }
	 for(int i=0;i<n;i++)
	    a[i]=a[i]*(i+2)-b[i];
	int m;
	cin>>m;
	while(m--)
	{
	    int i;
	    scanf("%d",&i);
	    printf("%d\n",a[i-1]);
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

int main(){

int N;

cin>>N;

int Q; int L; int R; int i; int M;

cin>>Q;

int arr[N]={0}; int p[N];

for(int i=1;i<5;i++){

    p[0]=a[0];

    p[i]=p[i-1]+a[i];

}

while(Q–){

cin>>L>>R;

arr[i]= arr[i]+(i-L+1);

}

cin>>M;

while(M–){

cin>>i;

cout<<arr[i]<<endl;

}

return 0;

}

can anyone help me how can i reduce it’s complexity??please

1 Like

My intuition is simpler than the editorial:

(1-L) and i are added seperately because i is not a constant.

1.Add (1-L) in the range [L,R] using a difference array (d1).
2.To add i, we will add 1 in the range [L,R] using a difference array (d2).
3.Finalize d1 and d2 by making it a prefix array.
4.Now, we will add i in d1, in those indexes of d1 where d2[ corresponding_indexes ] > 0 . So, add d2[i]*i to d1 using a running O(n) loop.

Time complexity - O(q+n+m)
My solution: Click Here