Increasing Decreasing Update Queries (Akku and Arrays)
Akku has solved many problems, she is a genius. One day her friend gave her an Array of sizes n and asked her to perform some queries of the following type:
Each query consists of three integers
1 A B: Update the Array at index A by value B
2 A B: if the subarray from index A to B (both inclusive) is
- Both increasing(Non-decreasing) and decreasing(Non-increasing) print -1
- Only increasing(Non-decreasing) print 0
- Only decreasing(Non-increasing) print 1
- Neither increasing nor decreasing print -1
Akku needs your help, can you help her?
Example:
Input: nums = {1,5,7,4,3,5,9}, queries = {{2,1,3},{1,7,4},{2,6,7}}
Output: {0,1}
Explanation:
For the 1st query given : A = 1, B = 3. From 1 to 3(1,5,7) elements are in increasing order. So answer is 0.
For the 2nd query we have to update the 7th element of the array by 4. So new updated array will be {1,5,7,4,3,5,4}
For the 3rd query A = 6, B = 7. From 6 to 7 (5, 4) elements are in descending order. So answer is 1.Input: nums = {3, 2, 5, 4, 7, 1, 6}, queries = {{2, 1, 3}, {1, 4, 6}, {2, 2, 5}, {1, 3, 8}}
Output: {-1, 0}
https://practice.w3wiki.net/problems/akku-and-arrays4452/1
Approach:
The idea is to use a segment tree data structure to store information about the subarrays of the given array. Each node of the segment tree represents a subarray and has four attributes: dec, inc, lm, and rm. These attributes indicate whether the subarray is decreasing, increasing, the leftmost and rightmost elements of the subarray respectively.
We are going to use the below function to execute our logic:
We’ll use two functions: merge() and update(). The merge function takes two nodes of the segment tree and returns a new node that represents the merged subarray of the two nodes. The update function modifies the segment tree by changing the value of a given index in the array and updating the nodes affected by the change.
We’ll also use a function called query() that takes a range of indices and returns the node that represents the subarray in that range. The function uses the merge function to combine the nodes that cover the range in the segment tree.
We’ll also use a function called solveQueries() that takes the array and the queries as input and returns a vector of integers as output. Iterates over the queries and performs the appropriate operation based on the query type.
- For query type 1, it calls the update function to change the value of the array at a given index.
- For query type 2, it calls the query function to get the node for the given range and then checks the attributes of the node to determine the answer.
The answer is -1 if the subarray is neither increasing nor decreasing, 0 if it is only increasing, 1 if it is only decreasing, and -1 if it is both increasing and decreasing. Finally, pushes the answer to the output vector and returns it at the end.
Steps:
- Initialize a segment tree data structure where each node stores information about a subarray of the input array. Each node should have four attributes: `dec`, `inc`, `lm`, and `rm`.
- Create a function to merge two nodes in the segment tree.
- It takes two nodes as input and returns a new node that represents the merged subarray. The new node’s attributes are determined based on the attributes of the input nodes.
- Create a function to update the segment tree when a value in the array is changed.
- It takes an index and a new value as input, changes the value at the given index in the array, and updates the corresponding nodes in the segment tree.
- Create a function to perform a query on the segment tree.
- It takes a range of indices as input and returns a node that represents the subarray in the given range. The returned node’s attributes are determined by merging the nodes that cover the range in the segment tree.
- Iterate over the queries. For each query, check the query type.
- If it’s an update query (type 1), call the update function with the given index and value.
- If it’s a subarray query (type 2), call the query function with the given range of indices, then check the returned node’s attributes to determine the answer. Store the answers in an array.
- After all queries have been processed, return the array of answers. Each answer corresponds to a subarray query in the input queries array, and is determined based on the attributes of the subarray in the segment tree.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define a class for the nodes in the segment tree class Node { public : bool dec = false ; // Indicates if the subarray is decreasing bool inc = false ; // Indicates if the subarray is increasing int lm = -1; // The leftmost element of the subarray int rm = -1; // The rightmost element of the subarray }; class Solution { public : vector<Node> seg; // The segment tree // Function to merge two nodes in the segment tree Node merge(Node& n1, Node& n2) { // If either of the nodes represents an empty // subarray, return the other node if (n1.lm == -1 || n2.lm == -1) return n1.lm == -1 ? n2 : n1; // Merge information from two nodes to update the // parent node Node ans; ans.lm = n1.lm; ans.rm = n2.rm; if (n1.inc && n2.inc && n1.rm <= n2.lm) ans.inc = true ; if (n1.dec && n2.dec && n1.rm >= n2.lm) ans.dec = true ; return ans; } // Function to update the segment tree void update( int idx, int l, int r, int & id, int & val) { // If the leaf node is reached, update it with the // new value if (l == r) { seg[idx] = { true , true , val, val }; return ; } // Otherwise, recursively update the appropriate // child node int mid = (l + r) / 2; if (id <= mid) update(2 * idx + 1, l, mid, id, val); else update(2 * idx + 2, mid + 1, r, id, val); // After updating the child nodes, merge their // information to update the current node seg[idx] = merge(seg[2 * idx + 1], seg[2 * idx + 2]); } // Function to perform a query on the segment tree Node query( int idx, int l, int r, int & ql, int & qr) { // If the current segment is completely outside the // query range, return an empty node if (ql > r || qr < l) return { false , false , -1, -1 }; // If the current segment is completely inside the // query range, return the node representing it if (ql <= l && qr >= r) return seg[idx]; // Otherwise, recursively query the child nodes and // merge their information int mid = (l + r) / 2; Node lq = query(2 * idx + 1, l, mid, ql, qr); Node rq = query(2 * idx + 2, mid + 1, r, ql, qr); return merge(lq, rq); } // Function to solve the queries vector< int > solveQueries(vector< int > nums, vector<vector< int > > queries) { vector< int > ans; int n = nums.size(); seg.resize(4 * n + 1); // Resize the segment tree to // accommodate the given array // Initializing the segment tree with the initial // array for ( int i = 0; i < n; i++) { update(0, 0, n - 1, i, nums[i]); } // Processing each query for ( auto it : queries) { int q = it[0]; int a = it[1] - 1; int b = it[2] - 1; if (q == 1) { // Update query: Increment the value at // index 'a' by 'b' update(0, 0, n - 1, a, ++b); } else { // Subarray query: Check properties of the // subarray from index 'a' to 'b' Node res = query(0, 0, n - 1, a, b); if (res.inc == res.dec) ans.push_back(-1); // Both increasing // and decreasing else if (res.dec) ans.push_back(1); // Only decreasing else ans.push_back(0); // Only increasing } } return ans; } }; int main() { Solution solution; vector< int > nums = { 1, 5, 7, 4, 3, 5, 9 }; vector<vector< int > > queries = { { 2, 1, 3 }, { 1, 7, 4 }, { 2, 6, 7 } }; vector< int > result = solution.solveQueries(nums, queries); cout << "Result: " ; for ( int res : result) { cout << res << " " ; } cout << endl; return 0; } |
Java
import java.util.*; class Node { boolean dec = false ; // Indicates if the subarray is decreasing boolean inc = false ; // Indicates if the subarray is increasing int lm = - 1 ; // The leftmost element of the subarray int rm = - 1 ; // The rightmost element of the subarray } public class Solution { ArrayList<Node> seg = new ArrayList<>(); // The segment tree // Function to merge two nodes in the segment tree Node merge(Node n1, Node n2) { // If either of the nodes represents an empty // subarray, return the other node if (n1.lm == - 1 || n2.lm == - 1 ) return n1.lm == - 1 ? n2 : n1; // Merge information from two nodes to update the // parent node Node ans = new Node(); ans.lm = n1.lm; ans.rm = n2.rm; if (n1.inc && n2.inc && n1.rm <= n2.lm) ans.inc = true ; if (n1.dec && n2.dec && n1.rm >= n2.lm) ans.dec = true ; return ans; } // Function to update the segment tree void update( int idx, int l, int r, int id, int val) { // If the leaf node is reached, update it with the // new value if (l == r) { seg.set(idx, new Node()); seg.get(idx).inc = true ; seg.get(idx).dec = true ; seg.get(idx).lm = val; seg.get(idx).rm = val; return ; } // Otherwise, recursively update the appropriate // child node int mid = (l + r) / 2 ; if (id <= mid) update( 2 * idx + 1 , l, mid, id, val); else update( 2 * idx + 2 , mid + 1 , r, id, val); // After updating the child nodes, merge their // information to update the current node seg.set(idx, merge(seg.get( 2 * idx + 1 ), seg.get( 2 * idx + 2 ))); } // Function to perform a query on the segment tree Node query( int idx, int l, int r, int ql, int qr) { // If the current segment is completely outside the // query range, return an empty node if (ql > r || qr < l) return new Node(); // If the current segment is completely inside the // query range, return the node representing it if (ql <= l && qr >= r) return seg.get(idx); // Otherwise, recursively query the child nodes and // merge their information int mid = (l + r) / 2 ; Node lq = query( 2 * idx + 1 , l, mid, ql, qr); Node rq = query( 2 * idx + 2 , mid + 1 , r, ql, qr); return merge(lq, rq); } // Function to solve the queries ArrayList<Integer> solveQueries(ArrayList<Integer> nums, ArrayList<ArrayList<Integer> > queries) { ArrayList<Integer> ans = new ArrayList<>(); int n = nums.size(); seg = new ArrayList<>(Collections.nCopies( 4 * n + 1 , new Node())); // Resize the segment tree to // accommodate the given array // Initializing the segment tree with the initial // array for ( int i = 0 ; i < n; i++) { update( 0 , 0 , n - 1 , i, nums.get(i)); } // Processing each query for (ArrayList<Integer> it : queries) { int q = it.get( 0 ); int a = it.get( 1 ) - 1 ; int b = it.get( 2 ) - 1 ; if (q == 1 ) { // Update query: Increment the value at // index 'a' by 'b' update( 0 , 0 , n - 1 , a, ++b); } else { // Subarray query: Check properties of the // subarray from index 'a' to 'b' Node res = query( 0 , 0 , n - 1 , a, b); if (res.inc == res.dec) ans.add(- 1 ); // Both increasing and // decreasing else if (res.dec) ans.add( 1 ); // Only decreasing else ans.add( 0 ); // Only increasing } } return ans; } public static void main(String[] args) { Solution solution = new Solution(); ArrayList<Integer> nums = new ArrayList<>( Arrays.asList( 1 , 5 , 7 , 4 , 3 , 5 , 9 )); ArrayList<ArrayList<Integer> > queries = new ArrayList<>(); queries.add( new ArrayList<>(Arrays.asList( 2 , 1 , 3 ))); queries.add( new ArrayList<>(Arrays.asList( 1 , 7 , 4 ))); queries.add( new ArrayList<>(Arrays.asList( 2 , 6 , 7 ))); ArrayList<Integer> result = solution.solveQueries(nums, queries); System.out.print( "Result: " ); for ( int res : result) { System.out.print(res + " " ); } System.out.println(); } } |
Python3
class Node: def __init__( self ): self .dec = False # Indicates if the subarray is decreasing self .inc = False # Indicates if the subarray is increasing self .lm = - 1 # The leftmost element of the subarray self .rm = - 1 # The rightmost element of the subarray class Solution: def __init__( self ): self .seg = [] # The segment tree # Function to merge two nodes in the segment tree def merge( self , n1, n2): # If either of the nodes represents an empty # subarray, return the other node if n1.lm = = - 1 or n2.lm = = - 1 : return n2 if n1.lm = = - 1 else n1 # Merge information from two nodes to update the # parent node ans = Node() ans.lm = n1.lm ans.rm = n2.rm if n1.inc and n2.inc and n1.rm < = n2.lm: ans.inc = True if n1.dec and n2.dec and n1.rm > = n2.lm: ans.dec = True return ans # Function to update the segment tree def update( self , idx, l, r, id , val): # If the leaf node is reached, update it with the # new value if l = = r: self .seg[idx] = Node() self .seg[idx].dec = True self .seg[idx].inc = True self .seg[idx].lm = val self .seg[idx].rm = val return # Otherwise, recursively update the appropriate # child node mid = (l + r) / / 2 if id < = mid: self .update( 2 * idx + 1 , l, mid, id , val) else : self .update( 2 * idx + 2 , mid + 1 , r, id , val) # After updating the child nodes, merge their # information to update the current node self .seg[idx] = self .merge( self .seg[ 2 * idx + 1 ], self .seg[ 2 * idx + 2 ]) # Function to perform a query on the segment tree def query( self , idx, l, r, ql, qr): # If the current segment is completely outside the # query range, return an empty node if ql > r or qr < l: return Node() # If the current segment is completely inside the # query range, return the node representing it if ql < = l and qr > = r: return self .seg[idx] # Otherwise, recursively query the child nodes and # merge their information mid = (l + r) / / 2 lq = self .query( 2 * idx + 1 , l, mid, ql, qr) rq = self .query( 2 * idx + 2 , mid + 1 , r, ql, qr) return self .merge(lq, rq) # Function to solve the queries def solveQueries( self , nums, queries): ans = [] n = len (nums) self .seg = [Node()] * ( 4 * n + 1 ) # Resize the segment tree to accommodate the given array # Initializing the segment tree with the initial # array for i in range (n): self .update( 0 , 0 , n - 1 , i, nums[i]) # Processing each query for it in queries: q, a, b = it a - = 1 b - = 1 if q = = 1 : # Update query: Increment the value at # index 'a' by 'b' self .update( 0 , 0 , n - 1 , a, b + 1 ) else : # Subarray query: Check properties of the # subarray from index 'a' to 'b' res = self .query( 0 , 0 , n - 1 , a, b) if res.inc = = res.dec: ans.append( - 1 ) # Both increasing and decreasing elif res.dec: ans.append( 1 ) # Only decreasing else : ans.append( 0 ) # Only increasing return ans solution = Solution() nums = [ 1 , 5 , 7 , 4 , 3 , 5 , 9 ] queries = [[ 2 , 1 , 3 ], [ 1 , 7 , 4 ], [ 2 , 6 , 7 ]] result = solution.solveQueries(nums, queries) print ( "Result:" , " " .join( map ( str , result))) |
C#
using System; using System.Collections.Generic; public class Node { public bool Dec = false ; // Indicates if the subarray is decreasing public bool Inc = false ; // Indicates if the subarray is increasing public int Lm = -1; // The leftmost element of the subarray public int Rm = -1; // The rightmost element of the subarray } public class Solution { private List<Node> seg; // The segment tree // Function to merge two nodes in the segment tree private Node Merge(Node n1, Node n2) { // If either of the nodes represents an empty subarray, return the other node if (n1.Lm == -1 || n2.Lm == -1) return n1.Lm == -1 ? n2 : n1; // Merge information from two nodes to update the parent node Node ans = new Node(); ans.Lm = n1.Lm; ans.Rm = n2.Rm; if (n1.Inc && n2.Inc && n1.Rm <= n2.Lm) ans.Inc = true ; if (n1.Dec && n2.Dec && n1.Rm >= n2.Lm) ans.Dec = true ; return ans; } // Function to update the segment tree private void Update( int idx, int l, int r, int id, int val) { // If the leaf node is reached, update it with the new value if (l == r) { seg[idx] = new Node { Inc = true , Dec = true , Lm = val, Rm = val }; return ; } // Otherwise, recursively update the appropriate child node int mid = (l + r) / 2; if (id <= mid) Update(2 * idx + 1, l, mid, id, val); else Update(2 * idx + 2, mid + 1, r, id, val); // After updating the child nodes, merge their information to update the current node seg[idx] = Merge(seg[2 * idx + 1], seg[2 * idx + 2]); } // Function to perform a query on the segment tree private Node Query( int idx, int l, int r, int ql, int qr) { // If the current segment is completely outside the query range, return an empty node if (ql > r || qr < l) return new Node(); // If the current segment is completely inside the query range, return the node representing it if (ql <= l && qr >= r) return seg[idx]; // Otherwise, recursively query the child nodes and merge their information int mid = (l + r) / 2; Node lq = Query(2 * idx + 1, l, mid, ql, qr); Node rq = Query(2 * idx + 2, mid + 1, r, ql, qr); return Merge(lq, rq); } // Function to solve the queries private List< int > SolveQueries(List< int > nums, List<List< int >> queries) { List< int > ans = new List< int >(); int n = nums.Count; seg = new List<Node>(); // Initializing the segment tree with the initial array for ( int i = 0; i < 4 * n + 1; i++) { seg.Add( new Node()); } for ( int i = 0; i < n; i++) { Update(0, 0, n - 1, i, nums[i]); } // Processing each query foreach (List< int > it in queries) { int q = it[0]; int a = it[1] - 1; int b = it[2] - 1; if (q == 1) { // Update query: Increment the value at index 'a' by 'b' Update(0, 0, n - 1, a, ++b); } else { // Subarray query: Check properties of the subarray from index 'a' to 'b' Node res = Query(0, 0, n - 1, a, b); if (res.Inc == res.Dec) ans.Add(-1); // Both increasing and decreasing else if (res.Dec) ans.Add(1); // Only decreasing else ans.Add(0); // Only increasing } } return ans; } public static void Main( string [] args) { Solution solution = new Solution(); List< int > nums = new List< int > { 1, 5, 7, 4, 3, 5, 9 }; List<List< int >> queries = new List<List< int >> { new List< int > { 2, 1, 3 }, new List< int > { 1, 7, 4 }, new List< int > { 2, 6, 7 } }; List< int > result = solution.SolveQueries(nums, queries); Console.Write( "Result: " ); foreach ( int res in result) { Console.Write(res + " " ); } Console.WriteLine(); } } |
Javascript
class Node { constructor() { this .Dec = false ; // Indicates if the subarray is decreasing this .Inc = false ; // Indicates if the subarray is increasing this .Lm = -1; // The leftmost element of the subarray this .Rm = -1; // The rightmost element of the subarray } } class Solution { constructor() { this .seg = []; // The segment tree } // Function to merge two nodes in the segment tree Merge(n1, n2) { // If either of the nodes represents an empty subarray, return the other node if (!n1 || !n2 || n1.Lm == -1 || n2.Lm == -1) return n1 && n1.Lm == -1 ? n2 : n1; // Merge information from two nodes to update the parent node const ans = new Node(); ans.Lm = n1.Lm; ans.Rm = n2.Rm; if (n1.Inc && n2.Inc && n1.Rm <= n2.Lm) ans.Inc = true ; if (n1.Dec && n2.Dec && n1.Rm >= n2.Lm) ans.Dec = true ; return ans; } // Function to update the segment tree Update(idx, l, r, id, val) { // If the leaf node is reached, update it with the new value if (l === r) { this .seg[idx] = new Node(); this .seg[idx].Inc = true ; this .seg[idx].Dec = true ; this .seg[idx].Lm = val; this .seg[idx].Rm = val; return ; } // Otherwise, recursively update the appropriate child node const mid = Math.floor((l + r) / 2); if (id <= mid) this .Update(2 * idx + 1, l, mid, id, val); else this .Update(2 * idx + 2, mid + 1, r, id, val); // After updating the child nodes, merge their information to update the current node this .seg[idx] = this .Merge( this .seg[2 * idx + 1], this .seg[2 * idx + 2]); } // Function to perform a query on the segment tree Query(idx, l, r, ql, qr) { // If the current segment is completely outside the query range, return an empty node if (ql > r || qr < l) return new Node(); // If the current segment is completely inside the query range, return the node representing it if (ql <= l && qr >= r) return this .seg[idx]; // Otherwise, recursively query the child nodes and merge their information const mid = Math.floor((l + r) / 2); const lq = this .Query(2 * idx + 1, l, mid, ql, qr); const rq = this .Query(2 * idx + 2, mid + 1, r, ql, qr); return this .Merge(lq, rq); } // Function to solve the queries SolveQueries(nums, queries) { const ans = []; const n = nums.length; this .seg = new Array(4 * n + 1).fill( null ); // Initializing the segment tree with the initial array for (let i = 0; i < n; i++) { this .Update(0, 0, n - 1, i, nums[i]); } // Processing each query for (const it of queries) { const q = it[0]; let a = it[1] - 1; let b = it[2] - 1; if (q === 1) { // Update query: Increment the value at index 'a' by 'b' this .Update(0, 0, n - 1, a, ++b); } else { // Subarray query: Check properties of the subarray from index 'a' to 'b' const res = this .Query(0, 0, n - 1, a, b); if (res.Inc === res.Dec) ans.push(-1); // Both increasing and decreasing else if (res.Dec) ans.push(1); // Only decreasing else ans.push(0); // Only increasing } } return ans; } } const solution = new Solution(); const nums = [1, 5, 7, 4, 3, 5, 9]; const queries = [ [2, 1, 3], [1, 7, 4], [2, 6, 7] ]; const result = solution.SolveQueries(nums, queries); console.log( "Result:" , result.join( " " )); //This code is contributed by Adarsh |
Result: 0 1
Time Complexity: O(N+QlogN), where N is the size of the input array, and Q is the number of queries.
Auxiliary Space: O(N)
Contact Us