Problem link: contest practice
Difficulty: Easy
Pre-requisites: Greedy, Segment tree
Problem: Given an array. Handle queries of updating it’s elements and output the size of the largest “nice” it’s consecutive subarray after processing each query. We consider an array nice if it’s elements form the increasing arithmetic progression with the difference of one.
Explanation:
Let’s consider different solutions to the calculation of the longest “nice” subarray problem.
At first, we can do a brute force over the beginning of the “nice” subarray and then try to add numbers to this subarray one-by-one, until there’s a number that makes the subarray “bad”. There are O(N) possible beginning positions and every beginning position check will take no more than O(N) time. So, we obtain O(N^2)-per-query solution that gets 20 points.
Then we can understand that different “nice” subarrays actually form a disjoint set of segments. By “segment” we understand a pair of numbers that describe a subarray by the leftmost and rightmost included in it numbers’ positions. We call a “disjoint set of segments” such set of segments that:
-
Every segment from it corresponds to some “nice” subarray;
-
Every segment in this set can not be extended without breaking the previous rule. By extension we understand decreasing the left border of a segment or increasing the right border;
-
The number of segments in the set is maximal.
It is easy to understand, that we can build such a set of segments greedily. More precisely, we can process the numbers of array in the order from the first to the last one. When we process the i-th number, we check, whether it can be added to the segment that corresponds to the i-1-th one. So, if the i-th number equals to the i-1-th one increased by one, we can increase the right border of the segment that corresponds to the i-1-th number. Otherwise, the i-th number is a start of some new segment (but it’s possible, that this new segment will correspond only to the i-th number).
So we can just find the longest segment in this set and output it’s size as an answer. If we do it in a naive way, we get 46 points, because it gives us O(N)-per-query solution.
This idea can be extended to the 100-point solution. Let’s maintain a segment tree that corresponds to some array B[] that consists of N-1 numbers. B[i] equals to one if the i-th and the i+1-th numbers of the original array belong to the same segment in the disjoint set of segments that was described above. Otherwise, B[i] equals to zero. Then, the problem transforms to the following one: answer the queries of the form
-
Change some B[i]. Possible, from zero to one, or vice-verse
-
Find the longest consecutive subarray of B[] that doesn’t contain ones.
It’s easy to see that the answer to the query of the second type increased by one is the answer to the original problem’s question. In order to perform these queries we can have a segment tree. In every node we will store:
-
the number of consecutive ones to the left of the beginning of the segment that corresponds to this node
-
the number of consecutive ones to the right of the end of the segment that corresponds to this node
-
the maximal possible group of consecutive ones that lies inside the segment that corresponds to this node
The recalculation of these values is straightforward and is one of the classical segment trees usage.
Summing up all the observations, we get O(log N)-per-query solution, where N is the number of numbers in the original array. The setter’s solution does actually the same, but uses a bit another trick that is also popular in the problems of this kind.
Setter’s solution: link
Tester’s solution: link