Calculate number of ways to partition array in groups of consecutive elements,so that for each group following condition holds:the length of group is not less than minimum element in that group and length of group is not greater than maximum element in that group.Each element must belong to exactly one group. Constraints: N <= 5*10^5 Ai <= 10^9
do with upper_bound() and lower_bound()
U cant brute this Should do with nlogn or sth
can you write a link on this ploblem, please
It isn't online
If this problem is related to some other contest that is still going on, then most likely no one will help you before it's over. Therefore, we need to know where this task comes from, otherwise it will be dishonest in relation to other participants
We can easily come up with an O(n2) DP recurrence: , where RMQ is the range maximum, and RMQ′ is the range minimum. Note that RMQ′ (i + 1, j) - (j - i) is an increasing function for a fixed j, so we can use two pointers to find all valid i.
We can dynamically maintain the suffix maxima as we use the two pointers algorithm using a deque of tuples
(left end, right end, maximum)
(shortened to(l, r, x)
). We are now going to add an extra fieldlz
to our tuple. If j ≥ lz, we are only going to add dpl + j - lz... r to dpj, instead of adding dpl... r. Note that lz = x + l + 1, so we can just sort our tuples by x + l + 1 in a set.This algorithm is slow if we have many tuples in our deque. However, its amortized time complexity is actually .