3748-count-stable-subarrays

3748. Count Stable Subarrays

Hard

---

You are given an integer array nums.

A subarray of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j].

You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri].

Return an integer array ans of length q, where ans[i] is the answer to the ith query.​​​​​​​​​​​​​​

Note:

• A single element subarray is considered stable.

 

Example 1:

Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]

Output: [2,3,4]

Explanation:​​​​​

• For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].

  <ul>
  	<li>The stable subarrays are <code>[3]</code> and <code>[1]</code>. The total number of stable subarrays is 2.</li>
  </ul>
  </li>
  <li>For <code>queries[1] = [1, 2]</code>, the subarray is <code>[nums[1], nums[2]] = [1, 2]</code>.
  <ul>
  	<li>The stable subarrays are <code>[1]</code>, <code>[2]</code>, and <code>[1, 2]</code>. The total number of stable subarrays is 3.</li>
  </ul>
  </li>
  <li>For <code>queries[2] = [0, 2]</code>, the subarray is <code>[nums[0], nums[1], nums[2]] = [3, 1, 2]</code>.
  <ul>
  	<li>The stable subarrays are <code>[3]</code>, <code>[1]</code>, <code>[2]</code>, and <code>[1, 2]</code>. The total number of stable subarrays is 4.</li>
  </ul>
  </li>
  

Thus, ans = [2, 3, 4].

Example 2:

Input: nums = [2,2], queries = [[0,1],[0,0]]

Output: [3,1]

Explanation:

• For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].

  <ul>
  	<li>The stable subarrays are <code>[2]</code>, <code>[2]</code>, and <code>[2, 2]</code>. The total number of stable subarrays is 3.</li>
  </ul>
  </li>
  <li>For <code>queries[1] = [0, 0]</code>, the subarray is <code>[nums[0]] = [2]</code>.
  <ul>
  	<li>The stable subarray is <code>[2]</code>. The total number of stable subarrays is 1.</li>
  </ul>
  </li>
  

Thus, ans = [3, 1].

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i] = [li, ri]
• 0 <= li <= ri <= nums.length - 1