1import java.util.*;
2
3class Solution {
4    private static final int MOD = 1_000_000_007;
5
6    /**
7     * An order-statistics multiset implemented over a TreeSet.
8     *
9     * Java's standard library lacks a built-in order-statistics tree (unlike the
10     * C++ pb_ds tree), so duplicates are allowed by pairing each value with a
11     * unique tie-breaker id. Keys {value, id} remain distinct while still
12     * sorting primarily by value, then by id.
13     *
14     * To support find-by-order in O(log n), we keep an auxiliary Fenwick (BIT)
15     * keyed by compressed values. The TreeSet alone cannot answer the k-th
16     * element query efficiently, so the BIT carries the rank information.
17     */
18    public int[] powerUpdate(int[] nums, int p, int[][] queries) {
19        int n = nums.length;
20        int q = queries.length;
21        int[] ans = new int[q];
22
23        // ----- Coordinate compression -----
24        // Collect every value that can ever appear (initial array + queries),
25        // so the Fenwick tree can be indexed by a small, dense range.
26        TreeSet<Integer> distinct = new TreeSet<>();
27        for (int x : nums) {
28            distinct.add(x);
29        }
30        for (int[] query : queries) {
31            distinct.add(query[0]);
32        }
33
34        // Map each distinct value to a 1-based compressed index.
35        Map<Integer, Integer> valueToIndex = new HashMap<>();
36        int idx = 1;
37        for (int value : distinct) {
38            valueToIndex.put(value, idx++);
39        }
40        int distinctCount = distinct.size();
41
42        // sortedValues[i] gives the original value for compressed index (i + 1).
43        int[] sortedValues = new int[distinctCount];
44        idx = 0;
45        for (int value : distinct) {
46            sortedValues[idx++] = value;
47        }
48
49        // ----- Fenwick tree (counts how many elements share each value) -----
50        // Acts as the order-statistics structure: prefix sums give ranks,
51        // and a binary-search descent gives the k-th element by order.
52        Fenwick fenwick = new Fenwick(distinctCount);
53
54        // Insert all initial numbers. The multiset semantics are handled by
55        // incrementing the count at the value's compressed index.
56        for (int x : nums) {
57            fenwick.update(valueToIndex.get(x), 1);
58        }
59
60        // ----- Answer each query -----
61        for (int i = 0; i < q; i++) {
62            int val = queries[i][0]; // value to insert before answering this query
63            int k = queries[i][1];   // we want the k-th largest value currently stored
64
65            // Insert the queried value (increment its count by one).
66            fenwick.update(valueToIndex.get(val), 1);
67
68            // The k-th largest element sits at ascending order index (size - k).
69            // findByOrder uses 0-based ordering, matching find_by_order.
70            int order = fenwick.size() - k;
71            int compressedIndex = fenwick.findByOrder(order);
72            int kthLargest = sortedValues[compressedIndex - 1];
73
74            // Each query is answered independently: compute p^(kthLargest) % MOD.
75            ans[i] = (int) modPow(p, kthLargest);
76        }
77
78        return ans;
79    }
80
81    /** Fast modular exponentiation: computes (base ^ exp) % MOD. */
82    private long modPow(long base, long exp) {
83        long result = 1;
84        base %= MOD;
85        while (exp > 0) {
86            if ((exp & 1) == 1) {
87                result = (result * base) % MOD;
88            }
89            base = (base * base) % MOD;
90            exp >>= 1;
91        }
92        return result;
93    }
94
95    /**
96     * A Fenwick (Binary Indexed) tree that supports point updates and the
97     * order-statistics queries needed here: total size and k-th element by
98     * order (0-based), both in O(log n).
99     */
100    private static class Fenwick {
101        private final int n;       // number of compressed value slots
102        private final int[] bit;   // 1-based Fenwick storage
103        private int total;         // running count of all inserted elements
104
105        Fenwick(int n) {
106            this.n = n;
107            this.bit = new int[n + 1];
108            this.total = 0;
109        }
110
111        /** Add delta to the count at compressed index i (1-based). */
112        void update(int i, int delta) {
113            total += delta;
114            for (; i <= n; i += i & (-i)) {
115                bit[i] += delta;
116            }
117        }
118
119        /** Current number of elements stored across all values. */
120        int size() {
121            return total;
122        }
123
124        /**
125         * Returns the 1-based compressed index of the element at the given
126         * 0-based order position. Equivalent to find_by_order: it locates the
127         * smallest index whose prefix count exceeds 'order'.
128         */
129        int findByOrder(int order) {
130            // 'order' is 0-based, so we search for the (order + 1)-th element.
131            int target = order + 1;
132            int pos = 0;
133            int remaining = target;
134
135            // Highest power of two not exceeding n.
136            int logN = Integer.highestOneBit(n);
137            for (int step = logN; step > 0; step >>= 1) {
138                int next = pos + step;
139                if (next <= n && bit[next] < remaining) {
140                    pos = next;
141                    remaining -= bit[next];
142                }
143            }
144            // pos now points to the last index with cumulative count < target,
145            // so the answer is the next index.
146            return pos + 1;
147        }
148    }
149}
150

1#include <ext/pb_ds/assoc_container.hpp>
2#include <ext/pb_ds/tree_policy.hpp>
3#include <vector>
4
5using namespace std;
6using namespace __gnu_pbds;
7
8// An order-statistics tree acting as an "ordered multiset".
9// Duplicates are allowed by pairing each value with a unique tie-breaker id,
10// so {value, id} keys remain distinct while still sorting primarily by value.
11template <typename T>
12using ordered_multiset = tree<pair<T, int>, null_type, less<pair<T, int>>,
13    rb_tree_tag, tree_order_statistics_node_update>;
14
15class Solution {
16public:
17    vector<int> powerUpdate(vector<int>& nums, int p, vector<vector<int>>& queries) {
18        vector<int> ans;
19        ordered_multiset<int> tree_set;          // ordered multiset of {value, unique_id}
20        const int mod = 1e9 + 7;
21
22        // Insert all initial numbers, using the array index as the unique id.
23        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
24            tree_set.insert({nums[i], i});
25        }
26
27        // Ids for values inserted by queries continue after the initial indices.
28        int next_id = static_cast<int>(nums.size());
29
30        // Fast modular exponentiation: computes (base ^ exp) % mod.
31        auto mod_pow = [&](long long base, long long exp) -> long long {
32            long long result = 1;
33            base %= mod;
34            while (exp > 0) {
35                if (exp & 1) {
36                    result = (result * base) % mod;
37                }
38                base = (base * base) % mod;
39                exp >>= 1;
40            }
41            return result;
42        };
43
44        for (const auto& query : queries) {
45            int val = query[0];   // value to insert before answering this query
46            int k = query[1];     // we want the k-th largest value currently stored
47
48            // Insert the queried value with a fresh unique id.
49            tree_set.insert({val, next_id++});
50
51            // The k-th largest element sits at index (size - k) in ascending order.
52            auto it = tree_set.find_by_order(tree_set.size() - k);
53            int kth_largest = it->first;
54
55            // Each query is answered independently: compute p^(kth_largest) % mod.
56            // (The original code reassigned p, which carried state between queries;
57            //  using a local result avoids that side effect.)
58            int result = static_cast<int>(mod_pow(p, kth_largest));
59            ans.push_back(result);
60        }
61
62        return ans;
63    }
64};
65

1/**
2 * Solves the powerUpdate problem.
3 *
4 * Since TypeScript/JavaScript has no built-in order-statistics tree,
5 * we emulate the "ordered multiset" with a sorted array. Each value is
6 * paired with a unique id so duplicate values remain distinct keys while
7 * still sorting primarily by value (and secondarily by id).
8 *
9 * @param nums    - initial numbers
10 * @param p       - exponentiation base
11 * @param queries - each query is [value, k]: insert `value`, then report
12 *                  p^(k-th largest value currently stored) % mod
13 * @returns the answer for each query
14 */
15function powerUpdate(nums: number[], p: number, queries: number[][]): number[] {
16    const ans: number[] = [];
17    const mod = 1_000_000_007n;
18
19    // The ordered multiset is represented as a sorted array of [value, id] pairs.
20    // We keep it sorted ascending by (value, id) so that index lookups behave
21    // like find_by_order on an order-statistics tree.
22    const sortedSet: Array<[number, number]> = [];
23
24    // Comparator: sort primarily by value, then by the unique tie-breaker id.
25    const compare = (a: [number, number], b: [number, number]): number => {
26        if (a[0] !== b[0]) {
27            return a[0] - b[0];
28        }
29        return a[1] - b[1];
30    };
31
32    // Find the leftmost insertion index that keeps the array sorted (lower_bound).
33    const lowerBound = (key: [number, number]): number => {
34        let low = 0;
35        let high = sortedSet.length;
36        while (low < high) {
37            const mid = (low + high) >>> 1;
38            if (compare(sortedSet[mid], key) < 0) {
39                low = mid + 1;
40            } else {
41                high = mid;
42            }
43        }
44        return low;
45    };
46
47    // Insert a [value, id] pair while preserving sorted order.
48    const insert = (key: [number, number]): void => {
49        const pos = lowerBound(key);
50        sortedSet.splice(pos, 0, key);
51    };
52
53    // Insert all initial numbers, using the array index as the unique id.
54    for (let i = 0; i < nums.length; ++i) {
55        insert([nums[i], i]);
56    }
57
58    // Ids for values inserted by queries continue after the initial indices.
59    let nextId = nums.length;
60
61    // Fast modular exponentiation: computes (base ^ exp) % mod using BigInt
62    // to avoid overflow during multiplication.
63    const modPow = (base: bigint, exp: bigint): bigint => {
64        let result = 1n;
65        base %= mod;
66        while (exp > 0n) {
67            if (exp & 1n) {
68                result = (result * base) % mod;
69            }
70            base = (base * base) % mod;
71            exp >>= 1n;
72        }
73        return result;
74    };
75
76    for (const query of queries) {
77        const val = query[0]; // value to insert before answering this query
78        const k = query[1];   // we want the k-th largest value currently stored
79
80        // Insert the queried value with a fresh unique id.
81        insert([val, nextId++]);
82
83        // The k-th largest element sits at index (size - k) in ascending order.
84        const kthLargest = sortedSet[sortedSet.length - k][0];
85
86        // Each query is answered independently: compute p^(kthLargest) % mod.
87        const result = Number(modPow(BigInt(p), BigInt(kthLargest)));
88        ans.push(result);
89    }
90
91    return ans;
92}
93