Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1622.html
1622. Fancy Sequence (Hard)
Write an API that generates fancy sequences using the append, addAll, and multAll operations.
Implement the Fancy class:
Fancy()Initializes the object with an empty sequence.void append(val)Appends an integervalto the end of the sequence.void addAll(inc)Increments all existing values in the sequence by an integerinc.void multAll(m)Multiplies all existing values in the sequence by an integerm.int getIndex(idx)Gets the current value at indexidx(0-indexed) of the sequence modulo109 + 7. If the index is greater or equal than the length of the sequence, return-1.
Example 1:
Input ["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"] [[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]] Output [null, null, null, null, null, 10, null, null, null, 26, 34, 20] Explanation Fancy fancy = new Fancy(); fancy.append(2); // fancy sequence: [2] fancy.addAll(3); // fancy sequence: [2+3] -> [5] fancy.append(7); // fancy sequence: [5, 7] fancy.multAll(2); // fancy sequence: [5*2, 7*2] -> [10, 14] fancy.getIndex(0); // return 10 fancy.addAll(3); // fancy sequence: [10+3, 14+3] -> [13, 17] fancy.append(10); // fancy sequence: [13, 17, 10] fancy.multAll(2); // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20] fancy.getIndex(0); // return 26 fancy.getIndex(1); // return 34 fancy.getIndex(2); // return 20
Constraints:
1 <= val, inc, m <= 1000 <= idx <= 105- At most
105calls total will be made toappend,addAll,multAll, andgetIndex.
Solution 1.
MOD = int(1e9 + 7)
class Node:
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) >> 1
self.v = 0
self.add = 0
self.mul = 1
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e5 + 1))
def modifyAdd(self, l, r, inc, node=None):
if l > r:
return
if node is None:
node = self.root
if node.l >= l and node.r <= r:
node.v = (node.v + (node.r - node.l + 1) * inc) % MOD
node.add += inc
return
self.pushdown(node)
if l <= node.mid:
self.modifyAdd(l, r, inc, node.left)
if r > node.mid:
self.modifyAdd(l, r, inc, node.right)
self.pushup(node)
def modifyMul(self, l, r, m, node=None):
if l > r:
return
if node is None:
node = self.root
if node.l >= l and node.r <= r:
node.v = (node.v * m) % MOD
node.add = (node.add * m) % MOD
node.mul = (node.mul * m) % MOD
return
self.pushdown(node)
if l <= node.mid:
self.modifyMul(l, r, m, node.left)
if r > node.mid:
self.modifyMul(l, r, m, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if l > r:
return 0
if node is None:
node = self.root
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v = (v + self.query(l, r, node.left)) % MOD
if r > node.mid:
v = (v + self.query(l, r, node.right)) % MOD
return v
def pushup(self, node):
node.v = (node.left.v + node.right.v) % MOD
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
left, right = node.left, node.right
if node.add != 0 or node.mul != 1:
left.v = (left.v * node.mul + (left.r - left.l + 1) * node.add) % MOD
right.v = (right.v * node.mul + (right.r - right.l + 1) * node.add) % MOD
left.add = (left.add * node.mul + node.add) % MOD
right.add = (right.add * node.mul + node.add) % MOD
left.mul = (left.mul * node.mul) % MOD
right.mul = (right.mul * node.mul) % MOD
node.add = 0
node.mul = 1
class Fancy:
def __init__(self):
self.n = 0
self.tree = SegmentTree()
def append(self, val: int) -> None:
self.n += 1
self.tree.modifyAdd(self.n, self.n, val)
def addAll(self, inc: int) -> None:
self.tree.modifyAdd(1, self.n, inc)
def multAll(self, m: int) -> None:
self.tree.modifyMul(1, self.n, m)
def getIndex(self, idx: int) -> int:
return -1 if idx >= self.n else self.tree.query(idx + 1, idx + 1)
# Your Fancy object will be instantiated and called as such:
# obj = Fancy()
# obj.append(val)
# obj.addAll(inc)
# obj.multAll(m)
# param_4 = obj.getIndex(idx)
############
# OJ: https://leetcode.com/problems/fancy-sequence/
# Time: O(1) for all
# Space: O(N)
# Ref: https://leetcode.com/problems/fancy-sequence/discuss/898753/Python-Time-O(1)-for-each
class Fancy:
def __init__(self):
self.A = []
self.add = [0]
self.mul = [1]
def append(self, val: int) -> None:
self.A.append(val)
self.add.append(self.add[-1])
self.mul.append(self.mul[-1])
def addAll(self, inc: int) -> None:
self.add[-1] += inc
def multAll(self, m: int) -> None:
self.add[-1] *= m
self.mul[-1] *= m
def getIndex(self, i: int) -> int:
if i >= len(self.A): return -1
m = self.mul[-1] // self.mul[i]
inc = self.add[-1] - self.add[i] * m
return int((self.A[i] * m + inc) % (10 ** 9 + 7))
Solution 2.
// OJ: https://leetcode.com/problems/fancy-sequence/
// Time: O(1) for all
// Space: O(N)
// Ref: https://leetcode.com/problems/fancy-sequence/discuss/898861/C%2B%2B-Math-Solution-O(1)-extra-space-and-O(1)-time-for-each
class Fancy {
typedef unsigned long UL;
UL mod = 1e9 + 7, len = 0, increment = 0, mul = 1, A[100001];
UL modPow(UL base, UL exp) {
UL ans = 1, p = base;
for (; exp; exp >>= 1) {
if (exp & 1) ans = (ans * p) % mod;
p = (p * p) % mod;
}
return ans;
}
public:
Fancy() {}
void append(int val) {
A[len++] = (((val - increment + mod) % mod) * modPow(mul, mod - 2)) % mod;
}
void addAll(int inc) {
increment = (increment + inc) % mod;
}
void multAll(int m) {
mul = (mul * m) % mod;
increment = (increment * m) % mod;
}
int getIndex(int i) {
return i >= len ? -1 : ((A[i] * mul) % mod + increment) % mod;
}
};