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.

# How to do armyofme?

Do you mind explaining your offline algo ?

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.

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

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

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.