A variant of "Good Subarrays" from Round 825

Revision en4, by blackc4, 2022-10-13 20:31:18

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.

Solution idea

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.

Monotonically increasing case

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English blackc4 2022-10-13 20:31:18 38 Tiny change: 'In hurry, ' -> 'EDIT: It's resolved; see comments.\n\nIn hurry, '
en3 English blackc4 2022-10-13 15:06:41 43
en2 English blackc4 2022-10-13 14:17:59 21 Tiny change: 'tes to $a$. Unlike' -> 'tes to $a$, where $q \le n$. Unlike' (published)
en1 English blackc4 2022-10-13 14:15:48 1355 Initial revision (saved to drafts)