Based from what mnaveenkumar has said, you can easily derive a O(N ^ 2) greedy solution: Treat opening boxes as ‘(’ and ‘)’, and each time add another pair of ‘(’ and ‘)’ at positions i and j.
What is the conditon for this to be valid? If i < j it’s sure to be valid. Else, the minimum prefix sum between these positions have to be 1.
So now, solve the task for these 2 independently.
1st task: Find max of Aj - Ai with j > i in array, with updates removing numbers. This is an easy segment tree problem, so I’ll jump to the second one.
2nd task: Given an array initially consisting of 0s. Queries are:
Add 1 to a range
Delete 1 from a range
For each consecutive range, find max(Ai) - min(Ai), and find max of this value over all ranges.
Remove some element.
Simply build another segment tree with each node managing:
Min of segment
Answer to segment if every element is erased by the min.
Longest prefix and suffix without a 0 if every element is erased by the min.
These 2 segment trees are enough to answer these questions, and the complexity is O(N * logN * logN)
you solved the last 3 problems of div1 in nov challenge(the toughest ones).just solve the easy ones ones for few challenges and become red(untrue to your handle)
