arrays - Tricky Data Structures and Algorithm Problem

Question

I am stuck on this one problem for over 2 days from a contest

NOTE: THE CONTEST IS ALREADY OVER. IT IS QUESTION 4 ON THIS CONTEST(CodeDrift: 2 Pointers)

Problem Statement

You are given an array of size N.
A subarray A[l..r] contains all the elements from A[l] to A[r] inclusive. A subarray is scaler subarray
if A[l] + A[r] ≡ max(A[l..r]) mod (B)
where B is an integer and max() function is maximum number in the subarray

Find the total number of scaler subarrays. Since the answer can be large return the answer modulo 10⁹ + 7

Problem Constraints

1 <= N, B <= 5*10⁵
1 <= A[i] <= 10⁹

---

Example Input

A : [8, 7]
B : 4

A : [4, 5, 3, 8, 8]
B : 5

A : [1, 10, 2, 5, 3, 6, 4]
B : 3

Corresponding Output

1

3

11

What i have tried so far

1. I tried to solve this naively using two loops in O(N²) time complexity but was not able to turn it into O(N log N)

2. I tried to do divide and conquer but was not able to get a merge step

3. If an array is an mountain then finding answer is easy . Just iterate for A[r]. Until the peak of the mountain, since max is same as A[r] in this region, it leaves to find A[l] ≡ 0 mod(B) in A[0..r].
   Now for the downhill slope one can partition the problem in 2 parts. A[0..peak] and part A(peak..ar].
   For part A[0..peak] max remains constant and we can look for (mx - A[r]) mod B in A[0..peak]
   For part A(peak, A[r]) if we take any element as A[l] then max is the same as A[l]. This implies a A[l..r] is scaler subarray if A[r] ≡ 0 mod(B). so all the elements in A(peak, A[r]] will form a subarray starting at itself and ending at A[r].

4. I tried to break the array in list of mountains and solve for mountain, but was unable to do the merge step, i.e; when A[l] and A[r] belong to different mountains.

5. I tried to do it using 2 pointers, cause all the problems in that contest was successfully solved using 2 pointer method. Also the name of contest is 2 pointers.

I hope this information is enough. For any other info or query please mention me in the comment

Answer 1

等待大神解答