Hello everyone,

Lately, I’ve been focusing on learning some specific types of dynamic programming, and right now my main target is "counting DP". I’m looking for resources—such as blogs or videos—that could help me understand this topic better.

If you also know of any interesting counting DP problems (preferably with ratings in the 1600–2000 range) that would be good for practice, I’d really appreciate it if you could share them.

Thanks in advance to anyone who shares helpful resources!

Recently, I have been exploring different problems, and I came across an interesting one. Problem Statement

You are given an integer n and an array a of length n. You are also given q queries.

In one operation, you may perform one of the following actions:

1. Select a strictly increasing subsequence of the array and remove it.

2. Select a strictly decreasing subsequence of the array and remove it.

Your task is: after each query, determine the minimum number of operations required to remove all elements from the array.

Queries

Each query provides two integers x and val. You must update the array as a[x] = val, then output the answer for the updated array.

Version 1:

1 <= n < 2 * 10^5, q = 0

Version 2:

1 <= n, q <= 2 * 10^5

Note: In this version, operation type 2 (removing a decreasing subsequence) is not allowed.

Version 3:

1 <= n, q <= 2 * 10^5 Both operation types are allowed.