O(nlogn/k) | Detailed Explanation | Longest Non Decreasing Subsequence
We need to find minumum number of operations to make following arrays non-decreasing. \n[arr[0], arr[k], arr[2k], ....]\n[arr[1], arr[k + 1], arr[2k + 1], ...]\
We need to find minumum number of operations to make following arrays non-decreasing. \n[arr[0], arr[k], arr[2k], ....]\n[arr[1], arr[k + 1], arr[2k + 1], ...]\n....\n[arr[k - 1], arr[2k - 1], ...]\n\nClearly, each arrary listed above is independent of others, and we just need to find the minumum operation number for each array and add up all numbers to get the final result.\n\nFor each array, the number of operations needed is equal to `length of this array` - `length of longest non decreasing sequence of this array`. So our next step is to find a way to get the `length of longest non decreasing sequence`.\n\nLuckily,  length of longest increasing sequence is a well-studied question, and there are already many smart solutions for it:\nhttps://leetcode.com/submissions/detail/603649213/\n\nAlthough you can solve it with O(n^2) dp, it\'s recommended to use binary search for the O(nlogn) time complexity:\n```\nclass Solution {\npublic:\n    int lengthOfLIS(vector<int>& nums) {\n        vector<int32_t> state;\n        for (int32_t val : nums) {\n            auto it {lower_bound(state.begin(), state.end(), val)};\n            if (state.cend() == it) {\n                state.push_back(val);\n            } else {\n                *it = val;\n            }       \n        }\n\n        return state.size();\n    }\n};\n```\n\n\n\nWith all said above, the solution for this questions is straightforward now. But just keep it in mind that you need to replace `lower_bound` binary search with `upper_bound` since this question is asking non-decreasing instead of increasing. That\'s it, cheers:\n\n```\nclass Solution {\npublic:\n    int kIncreasing(vector<int>& arr, int k) {\n        auto const n {static_cast<int32_t>(arr.size())};\n        int32_t ans {0};\n        for (int32_t start {0}; start < k; ++start) {       \n            vector<int32_t> state;\n            int32_t cnt {0};\n            for (int32_t i {start}; i < n; i += k) {\n                ++cnt;\n                auto it {upper_bound(state.begin(), state.end(), arr[i])};\n                if (it == state.end()) {\n                    state.push_back(arr[i]);\n                } else {\n                    *it = arr[i];\n                }\n            }\n            ans += (cnt - static_cast<int32_t>(state.size()));            \n        }\n        return ans;\n    }\n};\n```
['C', 'Binary Tree']