Question : We have been given two arrays of size N with each element as hi, ai the elements are positive integers and random. We are Also Given with Q queries of 2 type.
In query type 1 : we will be given with 2 positive integers b k and we have to update a[b] to k.
In query Type 2 : we will be given with 2 positive integers b c and we need to find out whether moving from h[b] to h[c] possible and if yes then we have to find a sum.
Now, there are rules to move in array h[i].
Rule 1 : We can only move from i to j if A[i] < A[j].
Rule 2 : We can only move to just next greatest element. i.e if array [1,5,4,8] and we want to move from 1 to 8, then path taken will be 1-->5-->8. we cannot take 1-->4-->8 as 4 is not the next greater element of 1.
Constraints :
1≤N,Q≤2⋅10^5
1≤hi≤10^9 for each valid i
1≤ai≤10^9 for each valid i
1≤b,c≤N
1≤k≤10^9
For each query of type 2 if it is possible to go from b to c then we have to output the sum of elements from a[i] that were part of path.
For Example h[] = {1,5,4,8} , a[] = {1,2,3,4}, path taken : 1-->5-->8 (b=1,c=4)so sum will be 1+2+4 = 7.
And if we cannot reach to destination for example h[] = {1,5,4,4} b=1,c=4 so here we cannot reach to 4th index by following rules of movement hence output will be -1.
What I have tried:
So, Now I think Question is clear. What i need to know is how to pre-process all this. i mean for every query of type 2 i can just create a loop and find we reaching from b to c is possible or not. But due to very large Queries the time complexity becomes O(n^2) of my approach which gives TLE. I need to know how to pre-process everything so that for every query of type 2 i just calculate the answer in constant time.
My O(n^2) approach.
while(Q--)
{
int q,b,c,k; cin >> q;
if(q == 1)
{
cin >> b >> k;
a[b]=k;
}
else
{
cin >> b >> c;
int sum = a[c],curr=a[b];bool flag = 0;
for( int i = b+1 ; i < c-1 ; i++ )
{
if( h[i] > curr )
{
sum+=a[i];
curr=h[i];
flag=1;
}
}
if(flag)
cout << sum << "\n";
else
cout << "-1\n";
}
}
So, My above approach works Fine when Q and N are below 1000, but when they are increased to 200000, this program gives TLE as for each query i am traversing a loop.
I need to remove this inner Loop, by doing some pre-processing before Query loop (while(Q--){..}). The problem is that i cant figure out how to pre-process the input data such that i am able to know that reaching from b to c is possible or not and if it is then calculating desired sum.
Please Help me out, I am scratching my head on this from past few days..
Link to original problem:
https://www.codechef.com/JULY20B/problems/DRGNDEN[
^]