Welcome to Subscribe On Youtube

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.

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


  • 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

All Problems

All Solutions