EDIT: It's resolved; see comments.
In hurry, I misread the "Good Subarrays" problems in Codeforces Round 825 (Div. 2) resulting in the following problems. The easy version is easier than the original easy, but I don't know if there is an $$$O(n)$$$ or $$$O(n\log n)$$$ algorithm for the corresponding hard version. I appreciate any hints towards $$$O(n)$$$ or $$$O(n\log n)$$$ algorithms.
New good arrays (easy version)
You are given an array $$$a = [a_1, \ldots, a_n]$$$. A position $$$i$$$ is good if $$$a_i \ge i$$$; a subarray $$$[a_{\ell},\ldots,a_r]$$$ is good if all the positions $$$\ell, \ell+1, \ldots, r$$$ are good. Find the number of good subarrays.
New good arrays (harder version)
Now you are, in addition, given $$$q$$$ updates to $$$a$$$, where $$$q \le n$$$. Unlike the original hard version, these updates are adaptive, i.e., they are not independent. Compute the number of good subarrays after each update. I claim that if the updates only increase the number, then again it is possible.
You can solve this even if they are not monotonic increasing. Maintain sizes of continuous segments. Only one size changes per query.
The problem is you need to update segment size for all the entries in the segment, which could be $$$\Theta(n)$$$. Or how do you suggest I determine the size of the segment to update given the position to update?
By "updates", I assumed that an update involves changing an element at a single index. You can maintain a set of pairs of continuous segments and make changes in the set to get your answer for each query.
Yes, that's what I meant by updates.
Sorry I don't understand what pair you're referring to when you say "pairs" of continuous segments. I'd appreciate if you elaborate your approach.
Suppose I just have one set of good indices, and one of the positions becomes bad. Splitting it into two sets is going to be a linear-time operation.
You have a set of pairs {l,r} where all indices l to r are good. These pairs will be disjoint. One or two elements of this set will change on an update. I think you can carry on the rest of the problem from here.