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?
Thanks in advance.

1 Like

Do you mind explaining your offline algo ?

1 Like

@reedef has explianed his approcah you can read it


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 :face_with_head_bandage: even though mkthnum on spoj is a similar idea on persistent segtree.
Good approach. I wish i had thought of this :face_with_raised_eyebrow:

Edit: btw what will you do of your username now :joy:

1 Like

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

1 Like

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.

1 Like