跳转至

3930. 插入后第 K 大更新的幂 II 🔒

题目描述

给定一个整数数组 nums 和一个整数 p。

同时给定一个二维整数数组 queries，其中每个 queries[i] = [vali, ki]。

对于每次查询：

  • 将 vali 插入到 nums。
  • 令 x 为当前 nums 中第 ki 个 最大 的元素。
  • 将 p 更新 为 px % (109 + 7)。

返回数组 ans，其中 ans[i] 表示在第 i 次查询后 p 的值。

 

示例 1：

输入：nums = [2], p = 4, queries = [[3,1],[1,2]]

输出：[64,4096]

解释：

i vali 当前
nums		 ki 第 ki
大		 p 新的 p = pk % (109 + 7)
0 3 [2, 3] 1 3 4 43 % (109 + 7) = 64
1 1 [2, 3, 1] 2 2 64 642 % (109 + 7) = 4096

因此，ans = [64, 4096]。

示例 2：

输入：nums = [7,5], p = 6, queries = [[4,3],[7,2]]

输出：[1296,220296870]

解释：

i vali 当前
nums		 ki 第 ki
大		 p 新的 p = pk % (109 + 7)
0 4 [7, 5, 4] 3 4 6 64 % (109 + 7) = 1296
1 7 [7, 5, 4, 7] 2 7 1296 12967 % (109 + 7) = 220296870

因此，ans = [1296, 220296870]。

 

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109
  • 1 <= queries.length <= 2 * 104
  • 1 <= vali <= 109
  • 1 <= ki <= n + i + 1

解法

方法一：有序列表

我们用一个有序列表 \(\textit{sl}\) 来维护当前的数组 \(nums\)。对于每次查询，我们将 \(val_i\) 插入到 \(\textit{sl}\) 中，然后找到 \(\textit{sl}\) 中第 \(k_i\) 个最大的元素 \(x\)，利用快速幂算法将 \(p\) 更新为 \(p^x \bmod (10^9 + 7)\)，并将更新后的 \(p\) 加入答案数组中。

时间复杂度 \(O((n + m) \log (n + m))\)，空间复杂度 \(O(n + m)\)，其中 \(n\) 和 \(m\) 分别是 \(\textit{nums}\) 和 \(\textit{queries}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def powerUpdate(
        self, nums: list[int], p: int, queries: list[list[int]]
    ) -> list[int]:
        ans = []
        sl = SortedList(nums)
        mod = 10**9 + 7
        for val, k in queries:
            sl.add(val)
            p = pow(p, sl[-k], mod)
            ans.append(p)
        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
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_multiset = tree<pair<T, int>, null_type, less<pair<T, int>>,
    rb_tree_tag, tree_order_statistics_node_update>;

class Solution {
public:
    vector<int> powerUpdate(vector<int>& nums, int p, vector<vector<int>>& queries) {
        vector<int> ans;
        ordered_multiset<int> sl;
        const int mod = 1e9 + 7;

        for (int i = 0; i < nums.size(); i++) {
            sl.insert({nums[i], i});
        }

        int next_id = nums.size();

        auto mod_pow = [&](long long base, long long exp) -> long long {
            long long result = 1;
            base %= mod;
            while (exp > 0) {
                if (exp & 1) result = (result * base) % mod;
                base = (base * base) % mod;
                exp >>= 1;
            }
            return result;
        };

        for (const auto& query : queries) {
            int val = query[0];
            int k = query[1];

            sl.insert({val, next_id++});

            auto it = sl.find_by_order(sl.size() - k);
            int kth_largest = it->first;

            p = mod_pow(p, kth_largest);
            ans.push_back(p);
        }

        return ans;
    }
};

评论