LC 3187. Peaks in Array

https://leetcode.com/problems/peaks-in-array/description/

Tag: Segment Tree
Rate: 2154

class Solution {
public:
    int seg[100010 << 2];

    void update(int node, int l, int r, int target, int num) {
        if (l + 1 == r) {
            seg[node] += num;
            return;
        }
        int mid = (l + r) >> 1;
        if (target < mid) update(node << 1, l, mid, target, num);
        else update(node << 1 | 1, mid, r, target, num);
        seg[node] = seg[node << 1] + seg[node << 1 | 1];
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (ql >= r || qr <= l) return 0;
        if (ql <= l && r <= qr) return seg[node];
        int mid = (l + r) >> 1;
        return query(node << 1, l, mid, ql, qr) + query(node << 1 | 1, mid, r, ql, qr);
    }

    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<bool> isPeak(n, false);
        for (int i = 1; i < n - 1; i++) {
            if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
                update(1, 0, n, i, 1);
                isPeak[i] = true;
            }
        }
        vector<int> ans;
        for (auto &q: queries) {
            if (q[0] == 1) {
                int cnt = query(1, 0, n, q[1] + 1, q[2]);
                ans.push_back(cnt);
            } else {
                int idx = q[1], val = q[2];
                nums[idx] = val;
                if (idx + 1 < n && isPeak[idx + 1] && nums[idx + 1] <= val) {
                    isPeak[idx + 1] = false;
                    update(1, 0, n, idx + 1, -1);
                }
                if (idx - 1 >= 0 && isPeak[idx - 1] && nums[idx - 1] <= val) {
                    isPeak[idx - 1] = false;
                    update(1, 0, n, idx - 1, -1);
                }
                if (idx + 1 < n && idx - 1 >= 0 && isPeak[idx] && (nums[idx - 1] >= val || nums[idx + 1] >= val)) {
                    isPeak[idx] = false;
                    update(1, 0, n, idx, -1);
                }
                if (idx - 1 >= 0 && idx + 1 < n && nums[idx - 1] < nums[idx] && nums[idx] > nums[idx + 1] && !isPeak[idx]) {
                    isPeak[idx] = true;
                    update(1, 0, n, idx, 1);
                }
                if (idx - 2 >= 0 && nums[idx - 2] < nums[idx - 1] && nums[idx - 1] > nums[idx] && !isPeak[idx - 1]) {
                    isPeak[idx - 1] = true;
                    update(1, 0, n, idx - 1, 1);
                }
                if (idx + 2 < n && nums[idx + 2] < nums[idx + 1] && nums[idx + 1] > nums[idx] && !isPeak[idx + 1]) {
                    isPeak[idx + 1] = true;
                    update(1, 0, n, idx + 1, 1);
                }
            }
        }
        return ans;
    }
};

就當作是回復一下 Segment Tree 的記憶