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)