Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of operation: choose some $l$ and $r$ ($0 \le l \le r \le N-1$) and set the values of $A[l],A[l+1],\ldots,A[r]$ to $k$, where $k \le A[i]$ for all $l \le i \le r$. Find out minimum operations to convert $A$ to $B$.
I was thinking about dynamic programming solution but could not figure it out.
Let distinct elements of $B$ be $b_1,b_2,\ldots$ where $b_1>b_2>\cdots$. There must be an optimal solution where it first sets a range to $k_1$ then set a range to $k_2$ and so on, such that $k_1\ge k_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k_1,k_2,\ldots\in\{b_1,b_2,\ldots\}$ (otherwise, say $k_i\notin\{b_1,b_2,\ldots\}$, one can delete the $i$th operation without changing the result).
Using the property above, we have the following greedy algorithm.
Let $B[i_1],B[i_2],\ldots$ ($i_1<i_2<\cdots$) be the greatest elements, i.e. $b_1$. The algorithm firstly sets $A[i_1],A[i_2],\ldots$ to $b_1$ using as little operations as possible. More specifically, it checks whether $A[i_1]>b_1$ to see whether an operation is required to set $A[i_1]$ to $b_1$. If so, it then checks whether $A[i_1+1],\ldots,A[i_2-1]\ge b_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A[i_2]$. It then goes on with $A[i_2],A[i_3],\ldots$ For example, say
A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2
Now $b_1=2$ and $i_1=0, i_2=2, i_3 = 4, i_4=6$. It requires 2 operations to set $A[i_1],A[i_2],\ldots$ to $b_1$: first setting $A[0], \ldots, A[2]$, then setting $A[6]$.
The algorithm then repeats the above process for $b_2,b_3,\ldots$
This algorithm runs in $O(n\log n)$.
*Note, for example, when dealing with $b_2$ instead of $b_1$, no operation can be performed on a range containing $i_j$ for some $j$, otherwise $A[i_j]$ will be less than $B[i_j]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b_m$ when dealing with $b_m$.