**update**of the sum data in case of Q1 with the

**difference**.

With memcpy you can copy a bunch of sum-elements of the result array. Pay attention to store the overwritten data at first.

See more:

Copy Code

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.

Copy Code

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--) // Q is total Queries { int q,b,c,k; cin >> q; if(q == 1) // query type 1 { cin >> b >> k; a[b]=k; } else // query type 2 { cin >> b >> c; int sum = a[c],curr=a[b];bool flag = 0; for( int i = b+1 ; i < c-1 ; i++ ) // loop to find sum if possible { if( h[i] > curr ) // h[i] is the just next greater. { 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[^]

Comments

Q1 is an changing task, but it only changes one value. So you can store the Q2 results in an array and only make an **update** of the sum data in case of Q1 with the **difference** .

With memcpy you can copy a bunch of sum-elements of the result array. Pay attention to store the overwritten data at first.

With memcpy you can copy a bunch of sum-elements of the result array. Pay attention to store the overwritten data at first.

Comments

Can you tell how to make a Q2 results array, i cant figure it out ??

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Giving code snipset that we can run is a good idea too.