🟢 3184. Count Pairs That Form a Complete Day I _

tags: 暴力法(Brute Force) 雜湊表(Hash Table) 模運算(Modulo)

本題與下一題相同，只差在數字範圍，建議直接使用下一題的解法。

題意

給定一個整數陣列 hours\text{hours}。返回有多少對 (i,j)(i, j) 滿足 i<ji < j 且 hours[i]+hours[j]\text{hours}[i] + \text{hours}[j] 為 2424 的整數倍數。

約束條件

  • 1≤n=hours.length≤1001 \leq n = \text{hours.length} \leq 100
  • 1≤hours[i]≤1091 \leq \text{hours}[i] \leq 10^9

思路：暴力法(Brute Force)

對於陣列中的每個元素 hours[i]\text{hours}[i]，我們遍歷其後面的所有元素 hours[j]\text{hours}[j]，其中 j>ij > i。然後，我們計算這兩個數的和 hours[i]+hours[j]\text{hours}[i] + \text{hours}[j] 是否是 2424 的整數倍數。如果符合條件，將答案加一。

由於 nn 最大為 100100，所以 O(n2)\mathcal{O}(n^2) 的暴力法是可以接受的。關於如何優化，請參考下一題。

複雜度分析

  • 時間複雜度：O(n2)\mathcal{O}(n^2) ，其中 nn 為陣列的長度。
  • 空間複雜度：O(1)\mathcal{O}(1) 。
1
2
3
4
5
6
7
8
9
class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        n = len(hours)
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                if (hours[i] + hours[j]) % 24 == 0:
                    ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int n = hours.size(), ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if ((hours[i] + hours[j]) % 24 == 0)
                    ans++;
        return ans;
    }
};

🟡 3185. Count Pairs That Form a Complete Day II _

tags: 雜湊表(Hash Table) 模運算(Modulo)

題意

給定一個整數陣列 hours\text{hours}。返回有多少對 (i,j)(i, j) 滿足 i<ji < j 且 hours[i]+hours[j]\text{hours}[i] + \text{hours}[j] 為 2424 的整數倍數。

約束條件

  • 1≤n=hours.length≤5⋅1051 \leq n = \text{hours.length} \leq 5 \cdot 10^5
  • 1≤hours[i]≤1091 \leq \text{hours}[i] \leq 10^9

思路：雜湊表(Hash Table) + 模運算(Modulo)

從上一題的暴力法中可以注意到，我們在考慮到 nums[i]nums[i] 時，只需要知道 左側 的數字中有多少個數字 yy 滿足 y+nums[i]≡0(mod24)y + nums[i] \equiv 0 \pmod{24}。這樣我們就可以在 O(1)\mathcal{O}(1) 的時間內計算出答案。

因此可以使用類似於 1. Two Sum 的方法，使用 雜湊表(Hash Table) 來記錄每個數字的出現次數，然後對於每個數字 xx，我們只需要查詢 24−(x mod 24)24 - (x \bmod{24}) 的出現次數即可。

但需要注意到存在一種特殊情況，即 x=0x = 0 的情況，此時 24−x=2424 - x = 24，可以使用 特判 或 二次取模 的方式來處理。

具體步驟如下：

  1. 建立一個大小為 2424 的陣列 cnt\text{cnt} 來記錄每個數字對 2424 取模後的出現次數。
  2. 遍歷 hours\text{hours} 陣列，對於每個元素 xx：
    • 計算 x mod 24x \bmod{24} (也就是小時數對 2424 取餘)
    • 如果 xx 不為 00，則將 cnt[24−x]\text{cnt}[24 - x] 加到答案 ans\text{ans} 上(因為 hours[i]+hours[j]=24\text{hours}[i] + \text{hours}[j] = 24 時，ii 和 jj 就是一對)；如果 xx 為 00，則將 cnt[0]\text{cnt}[0] 加到答案 ans\text{ans} 上。
    • 或是做二次取模，將 cnt[(24−x) mod 24]\text{cnt}[(24 - x) \bmod{24}] 加到答案 ans\text{ans} 上。
    • 將 cnt[x]\text{cnt}[x] 加 11，更新計數。
  3. 最後返回答案 ans\text{ans}。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n) ，其中 nn 為陣列的長度。
  • 空間複雜度：O(24)=O(1)\mathcal{O}(24) = \mathcal{O}(1) 。
1
2
3
4
5
6
7
8
9
10
class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        ans = 0
        cnt = [0] * 24
        for x in hours:
            x %= 24
            # ans += cnt[24 - x] if x != 0 else cnt[0] # 特判
            ans += cnt[(24 - x) % 24] # 二次取模
            cnt[x] += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        long long ans = 0;
        vector<int> cnt(24, 0);
        for (int x : hours) {
            x %= 24;
            // ans += (x != 0) ? cnt[24 - x] : cnt[0]; 
            ans += cnt[(24 - x) % 24];
            cnt[x]++;
        }
        return ans;
    }
};

類題

🟡 3186. Maximum Total Damage With Spell Casting _

tags: 動態規劃(DP) 記憶化搜索(Memoization) 打家劫舍

題意

一個魔法師能夠施放許多不同的魔法。

給定一個陣列 powerpower，其中每個元素表示一個魔法的傷害值，可能有多個魔法的傷害值相同。

但當魔法師決定施放一個傷害值為 power[i]power[i] 的魔法時，就無法再施放傷害值為 power[i]−2power[i] - 2、power[i]−1power[i] - 1、power[i]+1power[i] + 1 或 power[i]+2power[i] + 2 的魔法。

每個魔法最多只能被施放 一次。

返回這個魔法師能夠施放的 最大 可能總傷害值。

思路：基於值域的打家劫舍動態規劃(DP)

這個問題可以轉換成值域上的問題，由於任兩個施放的魔法之間的差值需超過 22，因此可以統計每個傷害值的出現次數，並將其排序，這樣就可以將問題轉換成 打家劫舍 問題。

若選擇施放一個傷害為 xx 的魔法，其他傷害值為 xx 的魔法也可以施放，因此其貢獻為 x×cnt[x]x \times \text{cnt}[x]，其中 cnt[x]\text{cnt}[x] 表示傷害值為 xx 的魔法的數量。

但由於任兩個施放的魔法之間的差值需超過 22，因此可以由小到大便利每個傷害值，對於每個傷害值 xx，若前一個鍵值為 yy，且 x−y>2x - y > 2，則可以從前一個鍵值 yy 轉移過來，否則只能繼續往前找能夠轉移的鍵值。但由於已經轉換為值域問題，因此每次轉移時，最多只要考慮前 33 個鍵值。

方法一：維護施放前 i 個魔法，且第 i 個魔法必須施放的最大總傷害

首先統計每個傷害值的出現次數，並將其鍵值排序，然後使用動態規劃來解決問題。

令 dp[i]dp[i] 表示以施放前 ii 個魔法，且第 ii 個魔法必須施放的最大總傷害，則可以寫出以下轉移式：

  • dp[i]={max⁡0≤j<ikeys[i]−keys[j]>2dp[j]}+keys[i]×cnt[keys[i]]dp[i] = \{ \max\limits_{\substack{ 0 \leq j < i \\ \text{keys}[i] - \text{keys}[j] > 2}} dp[j] \} + \text{keys}[i] \times \text{cnt}[\text{keys}[i]]

但是這樣會有大量的轉移，因此可以維護一個陣列 mxmx，其中 mx[i]=max⁡0≤j≤idp[j]mx[i] = \max\limits_{0 \leq j \leq i} dp[j] ，這樣就可以將轉移的時間從 O(n2)\mathcal{O}(n^2) 降為 O(n)\mathcal{O}(n)。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n) ，其中 nn 為鍵值的數量，也可以視為 powerpower 陣列的長度。
    • 統計每個傷害值的出現次數需要 O(n)\mathcal{O}(n) 時間。
    • 排序鍵值需要 O(nlog⁡n)\mathcal{O}(n \log n) 時間。
    • 動態規劃需要 O(n)\mathcal{O}(n) 時間，對於每個狀態，最多只要考慮三個轉移來源即可。
  • 空間複雜度：O(n)\mathcal{O}(n) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        keys = sorted(cnt.keys())
        m = len(keys)

        dp = [0] * m
        dp[0] = keys[0] * cnt[keys[0]]
        mx = [dp[0]] + [0] * m # mx[i] = max(dp[0], dp[1], ..., dp[i])
        for i in range(1, m):
            for j in range(i-1, -1, -1): # 由於是值域，每次最多考慮 3 個數
                if keys[i] - keys[j] <= 2:
                    continue
                # dp[i] = max(dp[i], dp[j]) # 可以維護 mx ，這樣就能用下面兩行取代，將 O(n^2) 降為 O(n)
                dp[i] = max(dp[i], mx[j])
                break
            dp[i] += keys[i] * cnt[keys[i]]
            mx[i] = max(mx[i - 1], dp[i])
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using LL = long long;

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> cnt;
        for (int x : power) cnt[x]++;
        vector<pair<int, int>> kv(cnt.begin(), cnt.end());
        sort(kv.begin(), kv.end());
        int m = kv.size();

        vector<LL> dp(m, 0), mx(m, 0);
        dp[0] = (LL)kv[0].first * kv[0].second;
        mx[0] = dp[0];
        for (int i = 1; i < m; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (kv[i].first - kv[j].first <= 2) continue;
                dp[i] = max(dp[i], mx[j]);
                break;
            }
            dp[i] += (LL)kv[i].first * kv[i].second;
            mx[i] = max(mx[i - 1], dp[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

方法二：維護前 i 個魔法的最大總傷害

與方法一相同，首先統計每個傷害值的出現次數，並將其鍵值排序，然後使用動態規劃來解決問題。但我們改成維護一個隨着魔法數量增加而更新的狀態，即考慮在前 ii 個魔法中能夠達到的最大總傷害值。

定義 dp[i]dp[i] 表示考慮到第 ii 個魔法時的最大總傷害，則可以寫出轉移式如下：

  • dp[i]=max⁡(dp[i−1],dp[j]+power[i]×cnt[power[i]])dp[i] = \max(dp[i-1], dp[j] + \text{power}[i] \times \text{cnt}[\text{power}[i]]) ，其中 jj 是最近的一個與第 ii 個魔法的傷害值相差超過 22 的魔法。
    • 不施放第 ii 個魔法，則 dp[i]=dp[i−1]dp[i] = dp[i-1] 。
    • 施放第 ii 個魔法，則我們需要找到前面最近的一個與第 ii 個魔法的傷害值相差超過 22 的魔法 jj ，此時 dp[i]=dp[j]+power[i]×cnt[power[i]]dp[i] = dp[j] + \text{power}[i] \times \text{cnt}[\text{power}[i]] 。
    • 兩者取最大值即可。
  • 最終答案即為 dp[m−1]dp[m-1] ，其中 mm 為傷害值的種類數。

這裡以 Top-down 記憶化搜索(Memoization) 的方式來實現，同樣可改成 Bottom-up 的方式。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n) ，其中 nn 為鍵值的數量，也可以視為 powerpower 陣列的長度。
    • 統計每個傷害值的出現次數需要 O(n)\mathcal{O}(n) 時間。
    • 排序鍵值需要 O(nlog⁡n)\mathcal{O}(n \log n) 時間。
    • 動態規劃需要 O(n)\mathcal{O}(n) 時間，對於每個 ii ，最多只要考慮前 33 個鍵值即可。
  • 空間複雜度：O(n)\mathcal{O}(n) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        cnt = Counter(power)
        keys = sorted(cnt.keys())
        m = len(keys)

        @cache
        def dfs(i: int) -> int: # 考慮到第 i 個數字時的最大總傷害
            if i < 0:
                return 0
            j = i - 1
            while j >= 0 and keys[i] - keys[j] <= 2:
                j -= 1
            return max(dfs(i - 1), dfs(j) + keys[i] * cnt[keys[i]])
        
        return dfs(m - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using LL = long long;

class Solution {
public:
    long long dfs(int i, vector<pair<int, int>>& kv, vector<LL>& memo) {
        if (i < 0) return 0;
        LL &res = memo[i];
        if (res != -1) return res;
        int j = i - 1;
        while (j >= 0 && kv[i].first - kv[j].first <= 2) j--;
        return res = max(dfs(i - 1, kv, memo), dfs(j, kv, memo) + (LL)kv[i].first * kv[i].second);
    }
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> cnt;
        for (int x : power) cnt[x]++;
        vector<pair<int, int>> kv(cnt.begin(), cnt.end());
        sort(kv.begin(), kv.end());
        int m = kv.size();
        vector<LL> memo(m, -1);
        return dfs(m - 1, kv, memo);
    }
};

類題

🔴 3187. Peaks in Array _

tags: 樹狀陣列(BIT) 線段樹(Segment Tree) 分治法(Divide and Conquer)

題意

定義一個陣列中的 峰值(Peak) 元素為 大於 前後相鄰元素的元素。

給定一個整數陣列 numsnums 和一個二維整數陣列 queriesqueries。

你需要處理以下兩種類型的查詢：

  • queries[i]=[1,li,ri]queries[i] = [1, l_i, r_i]，確定子陣列 nums[li..ri]nums[l_i..r_i] 中的 峰值 元素的數量。
  • queries[i]=[2,indexi,vali]queries[i] = [2, index_i, val_i]，將 nums[indexi]nums[index_i] 變為 valival_i。

返回一個陣列 answeranswer，依次包含每一個第一種查詢的答案。

注意：陣列或子陣列中的第一個和最後一個元素都 不能 是 峰值 元素。

思路：PURQ + 樹狀陣列(Binary Indexed Tree) / 線段樹(Segment Tree)

根據題意，我們需要做到 單點修改區間查詢(Point Update Range Query, PURQ) 的操作，為此可以使用 樹狀陣列(Binary Indexed Tree) 或 線段樹(Segment Tree) 來解決。

接下來就是要如何維護區間內的 峰值 元素的數量，這裡有兩種思路

  1. 維護峰值的位置，轉換為 區間求和 問題
  2. 維護區間內的峰值數量，轉換為 區間分治 問題。

方法一：維護峰值，轉換為區間求和問題

首先遍歷一次陣列，將每個峰值的位置記錄下來，然後使用 樹狀陣列(Binary Indexed Tree) 或 線段樹(Segment Tree) 來維護區間內的峰值數量，這裡使用樹狀陣列(Binary Indexed Tree) 來解決，關於其細節可以參考 树状数组从入门到下车 。

關於修改和查詢操作的說明如下：

  • 進行單點修改時，由於會變動的只有修改點以及其左右兩個點，總共三個位置，因此可以透過更新這三個位置是否為峰值，來更新區間內的峰值數量。
    • 更新時可以先檢查原本是否為峰值再進行修改，以避免修改前後的狀態相同，造成不必要的更新。
  • 進行區間查詢時，由於子陣列的頭尾元素不能是峰值，因此查詢時不能包含區間的頭尾，所以要查詢的區間為 [l+1,r−1][l+1, r-1]。
    • 但需注意當 l+1>r−1l+1 > r-1 時，為空區間，此時應該返回 00。

複雜度分析

  • 時間複雜度：O(n+qlog⁡n)\mathcal{O}(n + q \log n) ，其中 nn 為陣列的長度，qq 為查詢的個數。
    • 初始化 樹狀陣列(Binary Indexed Tree) 的時間複雜度為 O(n)\mathcal{O}(n) 。
    • 單點修改的時間複雜度為 O(log⁡n)\mathcal{O}(\log n) 。
    • 區間查詢的時間複雜度為 O(log⁡n)\mathcal{O}(\log n) 。
  • 空間複雜度：O(n)\mathcal{O}(n) ，不計算答案的空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class FenwickTree: # PURQ (Point Update Range Query), 1-based, initialization: O(n)
    __slots__ = 'nums', 'tree'

    def __init__(self, nums: List[int]): # 下標從 1 開始
        n = len(nums)
        self.nums = nums
        tree = [0] * (n + 1) # 下標從 1 開始
        for i, x in enumerate(nums, 1): # initialization: O(n)
            tree[i] += x
            nxt = i + (i & -i) # 下一個關鍵區間的右端點
            if nxt <= n:
                tree[nxt] += tree[i]
        self.tree = tree

    def add(self, k: int, x: int) -> None: # 令 nums[k] += x
        k += 1
        while k < len(self.tree):
            self.tree[k] += x
            k += (k & -k)

    def update(self, k: int, x: int) -> None: # 令 nums[k] = x
        self.add(k, x - self.nums[k])
        self.nums[k] = x

    def sum(self, l: int, r: int) -> int: # 區間查詢 (區間求和): 求 nums[l] 到 nums[r] 之和
        if l > r: # 本題中會出現 l > r 的情況
            return 0
        return self.preSum(r+1) - self.preSum(l)

    def preSum(self, k: int) -> int: # 求前綴和: 求 nums[0] 到 nums[k] 的區間和
        s = 0
        while k > 0:
            s += self.tree[k]
            k &= k - 1 # 等同 k -= (k & -k)
        return s
 
class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        # peaks[i] = 1 if nums[i-1] < nums[i] > nums[i+1]
        peaks = [0] + [1 if nums[i-1] < nums[i] > nums[i+1] else 0 for i in range(1, n-1)] + [0]
        bit = FenwickTree(peaks)
        ans = []
        for op, *args in queries:
            if op == 1:
                l, r = args
                ans.append(bit.sum(l+1, r-1)) # 不包含頭尾
            else:
                idx, val = args
                nums[idx] = val
                for i in range(idx-1, idx+2): # 更新 idx-1, idx, idx+1 三個位置
                    if i <= 0 or i >= n-1:
                        continue
                    if nums[i-1] < nums[i] > nums[i+1]: # 現在是峰值
                        if bit.nums[i] == 0: # 之前不是峰值
                            bit.update(i, 1)
                    else: # 現在不是峰值
                        if bit.nums[i] == 1: # 之前是峰值
                            bit.update(i, 0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class FenwickTree { // PURQ (Point Update Range Query), 1-based, initialization: O(n)
private:
    int n = 0;
    vector<int> tree;
public:
    vector<int> nums;
    FenwickTree(vector<int>& nums) {
        n = nums.size();
        this->nums = nums;
        tree = vector<int>(n + 1); // 1-based
        for (int i = 1; i <= n; i++) { // initialization: O(n)
            tree[i] += nums[i-1];
            int nxt = i + (i & -i); // 下一個關鍵區間的右端點
            if (nxt <= n) {
                tree[nxt] += tree[i];
            }
        }
    }

    void add(int k, int x) { // 令 nums[k] += x
        for (int i = k+1; i < tree.size(); i += i & -i) {
            tree[i] += x;
        }
    }

    void update(int k, int x) { // 令 nums[k] = x
        add(k, x - nums[k]);
        this->nums[k] = x;
    }

    int sum(int l, int r) { // 區間查詢 (區間求和): 求 nums[l] 到 nums[r] 之和
        if (l > r) return 0; // 本題中會出現 l > r 的情況
        return preSum(r+1) - preSum(l);
    }

    int preSum(int k) { // 求前綴和: 求 nums[0] 到 nums[k] 的區間和
        int s = 0;
        for (int i = k; i > 0; i -= i & -i) {
            s += tree[i];
        }
        return s;
    }
};
class Solution {
public:
    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> peaks(n, 0);
        for (int i = 1; i < n-1; i++)
            if (nums[i-1] < nums[i] && nums[i] > nums[i+1])
                peaks[i] = 1;
        FenwickTree bit(peaks);
        vector<int> ans;
        for (auto& q : queries) {
            if (q[0] == 1) {
                int l = q[1], r = q[2];
                ans.push_back(bit.sum(l+1, r-1)); // 不包含頭尾
            } else {
                int idx = q[1], val = q[2];
                nums[idx] = val;
                for (int i = idx-1; i <= idx+1; i++) { // 更新 idx-1, idx, idx+1 三個位置
                    if (i <= 0 || i >= n-1) continue;
                    if (nums[i-1] < nums[i] && nums[i] > nums[i+1]) { // 現在是峰值
                        if (bit.nums[i] == 0) // 之前不是峰值
                            bit.update(i, 1);
                    } else { // 現在不是峰值
                        if (bit.nums[i] == 1) // 之前是峰值
                            bit.update(i, 0);
                    }
                }
            }
        }
        return ans;
    }
};

方法二：以區間分治的方式維護峰值數量

在這個方法中，我們使用 線段樹(Segment Tree) 以區間合併的方式來維護區間內的峰值數量。為此需要定義合併函數 merge，該函數根據左右兩個子節點的結果計算出合併後的節點結果，合併方法如下：

  • 兩個區間合併時，會新增的峰值為左區間的最後一個元素和右區間的第一個元素。
    • 但由於這兩個元素相鄰，因此最多只有一個是峰值，因此可以使用 or 來合併。
  • 透過檢查這兩個元素是否為峰值，來更新合併後的區間的峰值數量。
  • 由於只要檢查兩個元素，因此 merge 可以在 O(1)\mathcal{O}(1) 的時間內完成。

使用線段樹維護若干區間的峰值數量，可以在 O(log⁡n)\mathcal{O}(\log n) 的時間內完成區間的查詢和修改操作，具體細節可參考 线段树从入门到急停 。程式碼的部分大部分都是模板，需要修改的地方主要是合併函數 merge 的部分。

複雜度分析

  • 時間複雜度：O(nlog⁡n+qlog⁡n)\mathcal{O}(n \log n + q \log n) ，其中 nn 為陣列的長度，qq 為查詢的個數。
    • 初始化 線段樹(Segment Tree) 的時間複雜度為 O(nlog⁡n)\mathcal{O}(n \log n) 。
    • 單點修改的時間複雜度為 O(log⁡n)\mathcal{O}(\log n) 。
    • 區間查詢的時間複雜度為 O(log⁡n)\mathcal{O}(\log n) 。
  • 空間複雜度：O(n)\mathcal{O}(n) ，不計算答案的空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class SegmentTree:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.n = n
        self.nums = [0] + nums # 讓 index 從 1 開始
        self.tree = [0 for _ in range(4 * n)]
        self.build(1, 1, n)
 
    def build(self, o, left, right): # node, left, right
        if left == right: # Leaf node initialization
            self.tree[o] = 0
            return
        mid = (left + right) // 2
        self.build(2*o, left, mid) # left child
        self.build(2*o+1, mid + 1, right) # right child
        self.tree[o] = self.merge(self.tree[2*o], self.tree[2*o+1], left, mid, right)

    # 合併 [left, mid] 和 [mid+1, right] 兩部分的結果
    def merge(self, left_part, right_part, left, mid, right):
        res = left_part + right_part
        # 檢查 mid 和 mid+1 是否為峰值，因為這兩種情況是互斥的，最多只會有一個成立，所以可以用 or 來合併
        if mid - 1 >= left and self.nums[mid-1] < self.nums[mid] > self.nums[mid+1] \
            or mid + 2 <= right and self.nums[mid] < self.nums[mid+1] > self.nums[mid+2]:
            res += 1
        return res

    def update(self, o, left, right, idx, val):
        if left == right:
            self.nums[idx] = val
            self.tree[o] = 0
            return
        mid = (left + right) // 2
        if idx <= mid:
            self.update(2*o, left, mid, idx, val)
        else:
            self.update(2*o+1, mid + 1, right, idx, val)
        self.tree[o] = self.merge(self.tree[2*o], self.tree[2*o+1], left, mid, right)
 
    def query(self, o, left, right, l, r):
        if left == l and r == right:
            return self.tree[o]
        mid = (left + right) // 2
        if r <= mid: # 只需要查詢左半部分
            return self.query(2*o, left, mid, l, r)
        if mid < l: # 只需要查詢右半部分
            return self.query(2*o+1, mid + 1, right, l, r)
        left_part = self.query(2*o, left, mid, l, mid)
        right_part = self.query(2*o+1, mid+1, right, mid+1, r)
        return self.merge(left_part, right_part, l, mid, r) # 合併左右兩部分
    
class Solution:
    def countOfPeaks(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        seg = SegmentTree(nums)
        ans = []
        for op, *args in queries:
            if op == 1:
                l, r = args
                ans.append(seg.query(1, 1, n, l+1, r+1))
            else:
                idx, val = args
                seg.update(1, 1, n, idx+1, val)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class SegmentTree {
private:
    vector<int> nums;
    vector<int> tree;
public:
    SegmentTree(vector<int>& nums) {
        int n = nums.size();
        this->nums = vector<int>(n + 1, 0);
        for (int i = 1; i <= n; i++) this->nums[i] = nums[i - 1]; // 1-indexed
        this->tree = vector<int>(4 * n, 0);
        build(1, 1, n);
    }

    void build(int o, int left, int right) {
        if (left == right) {
            tree[o] = 0;
            return;
        }
        int mid = (left + right) / 2;
        build(2 * o, left, mid);
        build(2 * o + 1, mid + 1, right);
        tree[o] = merge(tree[2 * o], tree[2 * o + 1], left, mid, right);
    }

    int merge(int l, int r, int left, int mid, int right) {
        int res = l + r;
        if (mid - 1 >= left && nums[mid-1] < nums[mid] && nums[mid] > nums[mid+1] ||
            mid + 2 <= right && nums[mid] < nums[mid+1] && nums[mid+1] > nums[mid+2])
            res += 1;
        return res;
    }

    void update(int o, int left, int right, int idx, int val) {
        if (left == right) {
            nums[idx] = val;
            tree[o] = 0;
            return;
        }
        int mid = (left + right) / 2;
        if (idx <= mid) update(2 * o, left, mid, idx, val);
        else update(2 * o + 1, mid + 1, right, idx, val);
        tree[o] = merge(tree[2 * o], tree[2 * o + 1], left, mid, right);
    }

    int query(int o, int left, int right, int l, int r) {
        if (left == l && r == right) return tree[o];
        int mid = (left + right) / 2;
        if (r <= mid) return query(2 * o, left, mid, l, r);  // 只需要查詢左半部分
        if (mid < l) return query(2 * o + 1, mid + 1, right, l, r);  // 只需要查詢右半部分
        int left_part = query(2 * o, left, mid, l, mid);  // 左半部分
        int right_part = query(2 * o + 1, mid + 1, right, mid + 1, r);  // 右半部分
        return merge(left_part, right_part, l, mid, r);  // 合併左右兩部分
    }
};

class Solution {
public:
    vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        SegmentTree seg(nums);
        vector<int> ans;
        for (auto& q : queries) {
            if (q[0] == 1) {
                int l = q[1], r = q[2];
                ans.push_back(seg.query(1, 1, n, l+1, r+1));
            } else {
                int idx = q[1], val = q[2];
                seg.update(1, 1, n, idx+1, val);
            }
        }
        return ans;
    }
};

參考資料

寫在最後

Cover photo is generated by @自由的风, thanks for their work!

I did not find any copyright declaration on the author’s personal page regarding permission or prohibition of use. Because of this, I used Pixiv.Cat to proxy the cover image. I actually do not save that image.

If the content of the article infringes on your copyright, please contact me through email or leave a comment to let me know, and I will promptly remove the relevant content.

睡到10:25才意識到今天要打周賽，還沒睡醒整個人都迷迷糊糊的，結果讓小號第一次掉分了，早知道就倒頭繼續睡 😂