We need to support 3 types of operations on an array a. Operation 1: Increment a[i] by 1.Operation 2: Find number of j such that a[j] ≥ x. Operation 3: For all j such that a[j] ≥ y, decrement a[j] by 1. N ≤ 100000, Q ≤ 1000000.
Check out the discussion responses for solution one hint at a time!
I got selection to IOITC this year. I would like to know more about the camp and topics which will be discussed there. Will they teach the whole syllabus of IOI in the camp within a span 10 days? What all should I learn before attending the camp in order to understand everything discussed there in a more better way?
Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i ... j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.
To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)
Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.