Apologies for two posts in one day.
A common DNC DP when partitioning arrays into K segments is to observe a monotonic property of [r, cost[l, r]] (I’m talking about the quadrangle inequality thing).
This often lends solutions to the form O(k n log n).
Typically we need to be able to get the cost of a partition, cost(l, r), in O(1) time. Sometimes this is not doable. Take this problem for example: https://codeforces.com/problemset/problem/833/B
The cost(l, r) is the # of unique elements in that subarray. This can be found online with a persistent seg tree in logN time, which makes the overall dnc dp O(k n log^2 n). This is a solution the editorial lists.
However I have observed some strong cf-ers seemingly combining mo’s algorithm, like two global pointers, with the recursive dnc dp. One of my ACs for that is here: https://codeforces.com/contest/833/submission/365023387
This solution is not listed in the editorial and in general I’ve had trouble finding any literature about this. This technique is using two global L and R pointers, allowing cost(l, r) updates to follow a mo’s-like pattern.
Is there any proof for the bounding of the asymptotics of this technique? Does my solution remain O(k n log n)? It seems to break multiple DNC DP questions.
I’ve also used it here (solution 2, the commented out code) to AC this 2500: https://codeforces.com/contest/1527/submission/365034845