Skip to content

3930. Power Update After K-th Largest Insertion II πŸ”’

Description

You are given an integer array nums and an integer p.

You are also given a 2D integer array queries, where each queries[i] = [vali, ki].

For each query:

  • Insert vali into nums.
  • Let x be the kith largest element in the current nums.
  • Update p to px % (109 + 7).

Return an array ans where the ans[i] represents the value of p after processing the ith query.

Β 

Example 1:

Input: nums = [2], p = 4, queries = [[3,1],[1,2]]

Output: [64,4096]

Explanation:

i vali Current
nums		 ki kith
largest		 p New 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

Thus, ans = [64, 4096].

Example 2:

Input: nums = [7,5], p = 6, queries = [[4,3],[7,2]]

Output: [1296,220296870]

Explanation:

i vali Current​​​​​​​
nums		 ki kith
largest		 p New 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

Thus, ans = [1296, 220296870]

Β 

Constraints:

  • 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​​​​​​​

Solutions

Solution 1: Sorted List

We use a sorted list \(\textit{sl}\) to maintain the current array \(nums\). For each query, we insert \(val_i\) into \(\textit{sl}\), then find the \(k_i\)-th largest element \(x\) in \(\textit{sl}\). Using fast exponentiation, we update \(p\) to \(p^x \bmod (10^9 + 7)\), and append the updated \(p\) to the answer array.

The time complexity is \(O((n + m) \log (n + m))\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the lengths of \(\textit{nums}\) and \(\textit{queries}\), respectively.

 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;
    }
};

Comments