Sorry for my poor English :) This is the online version.

Problem D. k-Maximum Subsequence Sum

Brief Description Giving a number sequence

Unable to parse markup [type=CF_TEX]

, in this sequence you need to implement the following two operations:

1. 0 x v: Change

   Unable to parse markup [type=CF_TEX]

   to

   Unable to parse markup [type=CF_TEX]

   .
2. 1 l r k: Query the k-MSS in

   Unable to parse markup [type=CF_TEX]

   .

Analysis

Consider the static problem, Apparently, we can use a dynamic programming to solve it.

1. Unable to parse markup [type=CF_TEX]

   : the j-MSS in [0, i].

2. Unable to parse markup [type=CF_TEX]

   : the quasi-j-MSS in [0, i], which the item

   Unable to parse markup [type=CF_TEX]

   must be selected.

The state transition is enumerating whether the

Unable to parse markup [type=CF_TEX]

time, and Query takes

Unable to parse markup [type=CF_TEX]

. It's too slow to get Accepted.

A simple optimization is using a data structure to speed up Query. The segment tree can be OK. In every node, we store such values in the interval represented by the node:

1. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments
2. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with the first element chosen
3. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with the last element chosen
4. the max sum if choosing

   Unable to parse markup [type=CF_TEX]

   subsegments with both first element and last element chosen

It's clear that if we know the values of two intervals

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, we can infer the values of the interval which is concatenating

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

by just enumerating how many subsegments can be chosen in

Unable to parse markup [type=CF_TEX]

and can be chosen in

Unable to parse markup [type=CF_TEX]

. The time complexity of concatenating two intervals is

Unable to parse markup [type=CF_TEX]

. So both operations Modify and Query take

Unable to parse markup [type=CF_TEX]

running time. The time limit is 5s in order to save Java's life. If you do some optimization, the solution can be Accepted. You can see liouzhou_101's solution for details.

It seems hard to be optimized using such idea. Now we are going to use another totally different idea from max-flow problem. We construct a max-cost max-flow model to solve this problem. The source is

Unable to parse markup [type=CF_TEX]

and the sink is

Unable to parse markup [type=CF_TEX]

. There are other

Unable to parse markup [type=CF_TEX]

vertices. A bi-directional edge between Vertex

Unable to parse markup [type=CF_TEX]

and Vertex

Unable to parse markup [type=CF_TEX]

has cost

Unable to parse markup [type=CF_TEX]

and capacity 1. The unidirectional edge from

Unable to parse markup [type=CF_TEX]

to Vertex

Unable to parse markup [type=CF_TEX]

has cost 0 and capacity 1 and the unidirectional edge from Vertex

Unable to parse markup [type=CF_TEX]

to

Unable to parse markup [type=CF_TEX]

has cost 0 and capacity 1. It's obvious for correctness. We can use Successive shortest path algorithm to solve the flow problem. But it's as slow as the brute-force method, or even worse.

Considering how the flow problem is solved, that is, how Successive shortest path algorithm works. We find the longest path(**max-cost** instead of min-cost ) between

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

, and then augment. We can simplify the algorithm due to the special graph. The new algorithm is:

1. find the subsegment with the maximum sum
2. negate the elements in the subsegment
3. repeat the two steps

   Unable to parse markup [type=CF_TEX]

   times
4. the answer is the sum of the sum of the subsegment you found each time.

So, the key point is doing these two operations quickly, where segment tree can possibly be used. To find the MSS you need to store

1. the sum of an interval
2. the maximum partial sum from left
3. the maximum partial sum from right
4. the MSS in the interval

To negate a subsegment, the minimum elements must be stored. To find the position of MSS, all the positions are supposed to be kept. The complexity of Modify is

Unable to parse markup [type=CF_TEX]

, and the complexity of Query is

Unable to parse markup [type=CF_TEX]

. It can pass all the test data easily but it has a really large constant. This is UESTC_Nocturne's solution and FattyPenguin's solution

The idea is hard to come up with and is also hard to code. So let's applaud again for UESTC_Nocturne and FattyPenguin. Also thanks for the great optimization of liouzhou_101.