from ARC114 ARC114C🤔
-
Thoughts.
-
I like to operate the C problem as v=min(A) throughout the first operation. Then you can solve the same problem by splitting it at each min(A) location. Now, if we look at the way the division is done, we can find the sum of “the number of A’s such that the interval l,r remains for all l,r,k (for v=k for the first operation) x f(r-l,M-k)”, which is O(N^2 M^2) if we keep the original problem answer as f(N,M), but if we use the cumulative sum, we get O(NM) if you use the cumulative sum tw.
This page is auto-translated from /nishio/ARC114C🤔 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.