Problem link: contest practice
Difficulty: Easy
Prerequisites: 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 onebyone, 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)perquery 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 ith number, we check, whether it can be added to the segment that corresponds to the i1th one. So, if the ith number equals to the i1th one increased by one, we can increase the right border of the segment that corresponds to the i1th number. Otherwise, the ith number is a start of some new segment (but it’s possible, that this new segment will correspond only to the ith 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)perquery solution.
This idea can be extended to the 100point solution. Let’s maintain a segment tree that corresponds to some array B[] that consists of N1 numbers. B[i] equals to one if the ith and the i+1th 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 viceverse

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)perquery 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