thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

class Solution:
    def countStableSubarrays(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        pos = []
        counter = []
        count = 1

        def f(l):
            return l * (l + 1) // 2
        for i in range(1, n):
            if nums[i - 1] > nums[i]:
                pos.append(i - 1)
                counter.append(f(count))
                count = 1
            else:
                count += 1

        pos.append(n - 1)
        counter.append(f(count))

        prefixSum = []
        sumSofar = 0
        for c in counter:
            sumSofar += c
            prefixSum.append(sumSofar)

        def query(l, r):
            if r < l:
                return 0
            if l == 0:
                return prefixSum[r]
            return prefixSum[r] - prefixSum[l - 1]

        ans = []
        for left, right in queries:
            l = bisect_left(pos, left)
            r = bisect_left(pos, right)

            if l == r:
                ans.append(f(right - left + 1))
                continue

            # middle full segments
            total = query(l + 1, r - 1)

            # left partial segment
            total += f(pos[l] - left + 1)

            # right partial segment
            total += f(right - pos[r - 1])

            ans.append(total)

        return ans
©leetcode

class Solution {
    public long[] countStableSubarrays(int[] nums, int[][] queries) {
        long[] f = preCalculateValidSubArray(nums);
        int[] left = preCalculateLeft(nums);
        int[] right = preCalculateRight(nums);

        long[] answer = new long[queries.length];
        int idx = 0;
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            if (l == r) {
                answer[idx] = 1;
                idx += 1;
                continue;
            }
            answer[idx] = f[r] - f[l] + 1 - (Math.min(right[l], r) - l) * left[l];
            idx += 1;
        }

        return answer;
    }

    public long[] preCalculateValidSubArray(int[] nums) {
        long[] valid = new long[nums.length];
        for (int i = 0; i < nums.length; i += 1) {
            if (i == 0 || nums[i] < nums[i - 1]) {
                valid[i] = 1;
            } else {
                valid[i] = valid[i - 1] + 1;
            }
        }
        for (int i = 1; i < nums.length; i += 1) {
            valid[i] += valid[i - 1];
        }

        return valid;
    }

    public int[] preCalculateLeft(int[] nums) {
        int[] left = new int[nums.length];
        for (int i = 0; i < nums.length; i += 1) {
            if (i == 0 || nums[i] < nums[i - 1]) {
                left[i] = 0;
            } else {
                left[i] = left[i - 1] + 1;
            }
        }

        return left;
    }

    public int[] preCalculateRight(int[] nums) {
        int[] right = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i -= 1) {
            if (i == nums.length - 1 || nums[i] > nums[i + 1]) {
                right[i] = i;
            } else {
                right[i] = right[i + 1];
            }
        }

        return right;
    }
}

public class Solution
{
    public class Segment
    {
        public int Start;
        public int End;
        public Segment(int start, int end)
        {
            Start = start;
            End = end;
        }
    }
    public long Count(Segment s) => Count(s.Start, s.End);
    //Count subarrays within range
    public long Count(int Start, int End)
    {
        long x = End - Start + 1;
        return x * (x + 1) / 2;
    }



    //Divide input array into non-decreasing segments
    //Output VVVVV
    int[] IdMap;// index -> seg id
    List<Segment> seg = new List<Segment>();
    public void map(int[] arr)
    {
        int id = 0;
        int n = arr.Length;
        IdMap = new int[n];
        for (int i = 0; i < n;)
        {
            int start = i;
            int j = i + 1;
            while (j < n && arr[j] >= arr[j - 1])
            {
                j++;
            }
            int end = j - 1;

            seg.Add(new Segment(start, end));
            for (int k = start; k <= end; k++)
            {
                IdMap[k] = id;
            }
            id++;
            i = j;
        }
    }


    public long[] CountStableSubarrays(int[] nums, int[][] queries)
    {
        map(nums);

        //Prefix sum of Subarrays within Segments
        long[] pref = new long[seg.Count];
        pref[0] =Count(seg[0]);
        for (int i = 1; i < seg.Count; i++)
            pref[i] = pref[i - 1] + Count(seg[i]);


        long[] rtn = new long[queries.Length];
        for (int i = 0; i < queries.Length; i++)
        {
            var t = queries[i];
            int left = t[0];
            int leftId = IdMap[left];
            int right = t[1];
            int rightId = IdMap[right];

            if (leftId == rightId)
            {
                rtn[i] = Count(left, right);
            }
            else
            {
                var middle = pref[rightId - 1] - pref[leftId];
                rtn[i] = middle + Count(left, seg[leftId].End) + Count(seg[rightId].Start,right);
            }
        }

        return rtn;
    }
}