Let’s find all prefix maximums in the original permutation. Clearly, they will be prefix maximums in any subsequence as well. Let’s call original prefix maximums special, and other elements not special.
Firstly, it’s clear that if the number of special elements is even, we can split: Just split them into two equal parts, and put the remaining elements in such a way that they don’t become prefix maximums. So we now assume that the number of special elements is odd, and there have to be some non-special elements that are prefix maximums in their subsequences.
Now, consider any splitting. Suppose that the first subsequence has a prefix maximum which is not special. Then, if we move this prefix maximum to the second subsequence, it will stop being prefix maximum, and the set of prefix maximums in the second subsequence won’t change. In the first subsequence, however, some new prefix maximums may appear. But we can keep moving the non-special prefix maximums to the second subsequence.
So, if the first subsequence has non-special prefix maximums, we can decrease its weight by one with this process without affecting the weight of the second subsequence.
Now, suppose that there is some splitting into two subsequences with equal weights. Suppose that both of them have some not special elements, which are their prefix maximums. Then we can apply this process to both subsequences, and decrease both of their weights by one. Keep doing this until we can. In the end, we will arrive at the valid splitting, where only one subsequence may contain non-special prefix maximums, let’s suppose that it’s the first one.
Let’s suppose that there are 2K+1 special elements in total and that in this valid splitting the first subsequence contains A of them, and the second contains 2K+1-A of them. Then the first subsequence has to contain additional 2K+1-2A non-special elements which are prefix maximums. So, in fact, we just have to check if there exists an increasing subsequence such that:
-
It contains at least 1 non-special element
-
The number of special elements$\times 2+$ the number of non-special elements is 2K+1.
This is easy to do with Segment Tree already. You can also use the following trick: “double” each special element, then we would just have to determine if there exists a non-decreasing subsequence of length at least 2K+1 which contains at least one non-special element. Then we just calculate for each element the length of the longest non-decreasing subsequence starting and ending at it, and check if some non-special element is contained in at least one of them.