+1

if there exist at least 1 value of x such that they form AP, the answer is distinct cnt, otherwise its distinct cnt + 1

Only first operation restricts us from removing all occurrences of some value at once, after that you can always rearrange in sorted order and remove any value directly since all values together can be removed as they are in AP.

so answer is atleast "number of distinct values in range", but you may not be able to remove all occurences of any value in first operation, so depending on that, answer will be distinct + 1 if you can't else its distinct.

now distinct is simple offline problem DQUERY

whats left is checking if any value in the range has all its occurences in AP of index.

this is offline too like you can do sweepline and find if any value has all it's occurences in AP inside range.

say right[i] stores rightmost index such that all occurences of arr[i] from i to right[i] are in AP of index, and then we sweep and maintain a value which covers query using segtree while sweeping.

Python Code

It's not hard to observe that the optimal path is a piecewise straight line, connecting the top of the towers, where all interior towers between two points lie on this piecewise straight line or below it. This gives the optimal path a convex hull structure as any valid line on the path would only bend right or remain straight (ignoring the first line which connects (0,0) and first brushed tower/point on the hull, which is trivially necessary).

So, the number of towers that Spiderman needs to brush is nothing but the number of points on the upper hull where we keep the collinear points too.

You can now refer to this article on CP Algorithms, to implement the algorithm to find the upper hull.

My AC Submission: 345958377

you can convert multiple modular multiplication operations into a single one. So all you need to know is the value k such that a[i] * k = b[i] mod (n + 1). Note that n + 1 might not always be prime, so you cant apply fermat's theorem to find the modular inverse, use extended gcd algo instead to find k for any one valid index and check if its same for all the indices.