» 8 years ago, # |   +3 It seems like it's possible to use a segment tree, but it's not necessary. A key insight that admits a priority queue based approach is that if you've flipped some segment, then later on find out that you can do better by not flipping it, you can "fix" the end result and pretend you never flipped that segment at all.Say you flip 3-7 here: 123456789 -+-+++-+- becomes 123456789 -++---++- But you later find out that you actually want to flip 1-3 and 7-9: 123456789 +-+++++-+ It's possible to quickly find and effect this "fix" operation using a priority queue.Actually, if you consider that you can just treat all contiguous runs of numbers of the same sign as single numbers, you can see that this is equivalent to finding a shortest augmenting path in a weighted bipartite graph.See http://codeforces.com/problemset/problem/280/D and the APIO task "Backup" for more.