I am not entirely sure my solution is correct. (Edit: It's correct)

I split the array in 2 sets, the one in the range [l, r] and what is left. In this sets we have the numbers sorted by indices in the initial array. We see that we only make swaps between numbers in different sets.

I did dp[i][j][cost] = the biggest amount of debt you can save if you make swaps till the ith from the first set and jth from the second set and spend cost kunas.

 dp[i][j][cost] = max (dp[i][j - 1][cost], dp[i - 1][j][cost], dp[i - 1][j - 1][cost - abs(x - y)] + a[x] - a[y]);

They should be up in a couple of minutes, I'll let you know,

Notice that n^2 is kinda (n / 2)^2, so it should pass (and 2e8 is kinda tight, 2e7 usually fits comfortably)

It should pass, 2e7 in 2 seconds shouldn't be tight at all.

Did you solve it for +? :)

You can use euler tour + segment tree + trie or dsu + trie(with lazy and a function for merge two tries) over the final tree, in both keep for every node of the trie the most "old" node in the subtree(necessary for search the maximum xor only with the nodes added before the current query)

I would say in an hour or so, but my hands are tied in that regard. I'll let you as soon as I hear the analysis mode is up.

Hi, I am coauthor of Holding and I was creating testcases for it. We have testcase on which your solution reaches the worst complexity, but running time of it is still low, 1.2sec, and time limit is 2sec. We couldn't put 1sec for time limit because some solutions with intended complexity were very close to 1sec.

I think I will

Problems are all available to submit: https://oj.uz/problems/source/445