One of them was Given an array of length n, and your task is to divide it into k subarrays. The cost of a subarray (i….j) is the (a[i] + a[i + 1]….+a[j])^2. Find the minimum Total Cost. The second was based on segment trees. The third was based on a Disjoint set Union (which was not easy to implement). Last one I didn’t remember.