How to do armyofme?

[anon25504910]

I solved all other problems in jan20A, and got partial on this. However no matter what i tried I couldn’t get this problem. I did come up with an offline algo with two stacks, a segtree and mo’s algorithm however i don’t know how to do the queries online.
Can one of the 22 guys who got 100 or someone else outline their solution?
Thanks in advance.

[harshraj22]

Do you mind explaining your offline algo ?

[divaskumar3110]

@reedef has explianed his approcah you can read it

DFMTRX Video Solution

What I did was: First, you concentrate on the gaps between elements of the permutation instead of the elements themselves Then you calculate, for each of those gaps, the smallest set of gaps that contains it and follows the requirements of the problem. Using a persistent segtree, you use the previous point together with some of the properties you deduce from the construction to compute the answer. For 2), we first compute a ‘necessary range’ for each gap. Given the gap between elements i and i…

[just1star]

I will try to explain a much more obvious and easier - to - implement idea.
To answer queries in offline, notice the condition of a subarray [L…R] to be good is basically R - L = max - min. So fix L, we have L = R - max + min.
In addition, max - min >= R - L. So L >= R - max + min.
If we fix L we want to maintain this value for each R bound. 2 stacks can be used and transform these to just range updates of “Erase X from this range”.
Since the value at L is always L, and every value after it is <= L, all the valid Rs will be the positions holding maximum values right now. So for these R bounds, set their “answer” value to R - L + 1. Use lazy to make this faster. Then a query is just finding the maximum answer value in the range.

For online queries implement persistent.

[anon25504910]

This is exactly the approach i took, but I couldn’t figure out the persistent segtree part even though mkthnum on spoj is a similar idea on persistent segtree.
Good approach. I wish i had thought of this

Edit: btw what will you do of your username now

[anon25504910]

Mine is exactly the same as just1star s approach but without the segtree part. Now i feel kind of doofish for missing it though, since just a week ago id done mkthnum on spoj whose idea is also to make queries online using persistent segtree

[harshraj22]

Wow. I could think only upto R-L=max-min part. After that I was lost thinking how to reduce time complexity. Constraints made me think about sqrt decomposition, but I couldn’t get any clue how to use it.