# How to do armyofme?

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?

1 Like

Do you mind explaining your offline algo ?

1 Like

@reedef has explianed his approcah you can read it

2 Likes

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.

3 Likes

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

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.