Welcome to Subscribe On Youtube

1622. Fancy Sequence

Description

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 integer val to the end of the sequence.
• void addAll(inc) Increments all existing values in the sequence by an integer inc.
• void multAll(m) Multiplies all existing values in the sequence by an integer m.
• int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 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 <= 100
• 0 <= idx <= 105
• At most 105 calls total will be made to append, addAll, multAll, and getIndex.

Solutions

Solution 2: Math + Modular Inverse

Thinking

The segment tree still walks $O(\log n)$ nodes on every update. addAll and multAll always hit every number already in the sequence, and a newly appended number is not changed by earlier adds or multiplies.

So every number already present will go through the same later adds and multiplies. We only need two global variables: how much those numbers should still be multiplied by, and how much should then be added. The array stores the value before those operations; a query multiplies and adds to recover the true value. The modulus is prime, so division by $a$ becomes multiplication by the modular inverse (Fermat’s little theorem).

Every addAll and multAll applies to all numbers that exist at that moment, and a number appended later is not affected by earlier updates. Therefore the pending multiply and add for every current number can be described by two global variables: multiply by $a$, then add $b$. Initially $a=1$ and $b=0$.

The array nums does not store the current true values. It stores the values before multiplying by $a$ and adding $b$, so that at any time

\[\text{true value} = (a \times \textit{nums}[i] + b) \bmod (10^9+7)\]

The operations then become:

• append(val): this new number has not gone through the current $a$ and $b$, so we store an $x$ with $a \times x + b = \textit{val}$, i.e. $x = (\textit{val} - b) \times a^{-1}$;
• addAll(inc): every true value increases by $inc$, so we add $inc$ to $b$;
• multAll(m): every true value is multiplied by $m$, so both $a$ and $b$ are multiplied by $m$;
• getIndex(idx): return $-1$ if the index is out of range, otherwise $a \times \textit{nums}[idx] + b$.

Here $a^{-1}$ is the modular inverse of $a$ modulo $10^9+7$. The modulus is prime, so Fermat’s little theorem gives $a^{-1} \equiv a^{MOD-2} \pmod{MOD}$.

All operations except the inverse in append run in $O(1)$ time; the inverse is $O(\log MOD)$. The space complexity is $O(n)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Node {
      Node left;
      Node right;
      int l;
      int r;
      int mid;
      long v;
      long add;
      long mul = 1;
  
      public Node(int l, int r) {
          this.l = l;
          this.r = r;
          this.mid = (l + r) >> 1;
      }
  }
  
  class SegmentTree {
      private Node root = new Node(1, (int) 1e5 + 1);
      private static final int MOD = (int) 1e9 + 7;
  
      public SegmentTree() {
      }
  
      public void modifyAdd(int l, int r, int inc) {
          modifyAdd(l, r, inc, root);
      }
  
      public void modifyAdd(int l, int r, int inc, Node node) {
          if (l > r) {
              return;
          }
          if (node.l >= l && node.r <= r) {
              node.v = (node.v + (node.r - node.l + 1) * inc) % MOD;
              node.add = (node.add + inc) % MOD;
              return;
          }
          pushdown(node);
          if (l <= node.mid) {
              modifyAdd(l, r, inc, node.left);
          }
          if (r > node.mid) {
              modifyAdd(l, r, inc, node.right);
          }
          pushup(node);
      }
  
      public void modifyMul(int l, int r, int m) {
          modifyMul(l, r, m, root);
      }
  
      public void modifyMul(int l, int r, int m, Node node) {
          if (l > r) {
              return;
          }
          if (node.l >= l && node.r <= r) {
              node.v = (node.v * m) % MOD;
              node.add = (node.add * m) % MOD;
              node.mul = (node.mul * m) % MOD;
              return;
          }
          pushdown(node);
          if (l <= node.mid) {
              modifyMul(l, r, m, node.left);
          }
          if (r > node.mid) {
              modifyMul(l, r, m, node.right);
          }
          pushup(node);
      }
  
      public int query(int l, int r) {
          return query(l, r, root);
      }
  
      public int query(int l, int r, Node node) {
          if (l > r) {
              return 0;
          }
          if (node.l >= l && node.r <= r) {
              return (int) node.v;
          }
          pushdown(node);
          int v = 0;
          if (l <= node.mid) {
              v = (v + query(l, r, node.left)) % MOD;
          }
          if (r > node.mid) {
              v = (v + query(l, r, node.right)) % MOD;
          }
          return v;
      }
  
      public void pushup(Node node) {
          node.v = (node.left.v + node.right.v) % MOD;
      }
  
      public void pushdown(Node node) {
          if (node.left == null) {
              node.left = new Node(node.l, node.mid);
          }
          if (node.right == null) {
              node.right = new Node(node.mid + 1, node.r);
          }
          if (node.add != 0 || node.mul != 1) {
              Node left = node.left, right = node.right;
              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 {
      private int n;
      private SegmentTree tree = new SegmentTree();
  
      public Fancy() {
      }
  
      public void append(int val) {
          ++n;
          tree.modifyAdd(n, n, val);
      }
  
      public void addAll(int inc) {
          tree.modifyAdd(1, n, inc);
      }
  
      public void multAll(int m) {
          tree.modifyMul(1, n, m);
      }
  
      public int getIndex(int idx) {
          return idx >= n ? -1 : tree.query(idx + 1, idx + 1);
      }
  }
  
  /**
   * Your Fancy object will be instantiated and called as such:
   * Fancy obj = new Fancy();
   * obj.append(val);
   * obj.addAll(inc);
   * obj.multAll(m);
   * int param_4 = obj.getIndex(idx);
   */
  
  
  // Solution 2
  class Fancy {
      private static final int MOD = (int) 1e9 + 7;
      private List<Integer> nums = new ArrayList<>();
      private long a = 1, b;
  
      public void append(int val) {
          long x = (val - b + MOD) % MOD * qpow(a, MOD - 2) % MOD;
          nums.add((int) x);
      }
  
      public void addAll(int inc) {
          b = (b + inc) % MOD;
      }
  
      public void multAll(int m) {
          a = a * m % MOD;
          b = b * m % MOD;
      }
  
      public int getIndex(int idx) {
          if (idx >= nums.size()) {
              return -1;
          }
          return (int) ((a * nums.get(idx) + b) % MOD);
      }
  
      private long qpow(long x, int n) {
          long res = 1;
          while (n > 0) {
              if ((n & 1) == 1) {
                  res = res * x % MOD;
              }
              x = x * x % MOD;
              n >>= 1;
          }
          return res;
      }
  }
  
  

• const int MOD = 1e9 + 7;
  
  class Node {
  public:
      Node* left;
      Node* right;
      int l;
      int r;
      int mid;
      long long v;
      long long add;
      long long mul;
  
      Node(int l, int r) {
          this->l = l;
          this->r = r;
          this->mid = (l + r) >> 1;
          this->left = this->right = nullptr;
          v = add = 0;
          mul = 1;
      }
  };
  
  class SegmentTree {
  private:
      Node* root;
  
  public:
      SegmentTree() {
          root = new Node(1, 1e5 + 1);
      }
  
      void modifyAdd(int l, int r, int inc) {
          modifyAdd(l, r, inc, root);
      }
  
      void modifyAdd(int l, int r, int inc, Node* node) {
          if (l > r) return;
          if (node->l >= l && node->r <= r) {
              node->v = (node->v + (node->r - node->l + 1) * inc) % MOD;
              node->add = (node->add + inc) % MOD;
              return;
          }
          pushdown(node);
          if (l <= node->mid) modifyAdd(l, r, inc, node->left);
          if (r > node->mid) modifyAdd(l, r, inc, node->right);
          pushup(node);
      }
  
      void modifyMul(int l, int r, int m) {
          modifyMul(l, r, m, root);
      }
  
      void modifyMul(int l, int r, int m, Node* node) {
          if (l > r) return;
          if (node->l >= l && node->r <= r) {
              node->v = (node->v * m) % MOD;
              node->add = (node->add * m) % MOD;
              node->mul = (node->mul * m) % MOD;
              return;
          }
          pushdown(node);
          if (l <= node->mid) modifyMul(l, r, m, node->left);
          if (r > node->mid) modifyMul(l, r, m, node->right);
          pushup(node);
      }
  
      int query(int l, int r) {
          return query(l, r, root);
      }
  
      int query(int l, int r, Node* node) {
          if (l > r) return 0;
          if (node->l >= l && node->r <= r) return node->v;
          pushdown(node);
          int v = 0;
          if (l <= node->mid) v = (v + query(l, r, node->left)) % MOD;
          if (r > node->mid) v = (v + query(l, r, node->right)) % MOD;
          return v;
      }
  
      void pushup(Node* node) {
          node->v = (node->left->v + node->right->v) % MOD;
      }
  
      void pushdown(Node* node) {
          if (!node->left) node->left = new Node(node->l, node->mid);
          if (!node->right) node->right = new Node(node->mid + 1, node->r);
          if (node->add || node->mul != 1) {
              long add = node->add, mul = node->mul;
              Node* left = node->left;
              Node* right = node->right;
              left->v = (left->v * mul + (left->r - left->l + 1) * add) % MOD;
              right->v = (right->v * mul + (right->r - right->l + 1) * add) % MOD;
              left->add = (left->add * mul + add) % MOD;
              right->add = (right->add * mul + add) % MOD;
              left->mul = (left->mul * mul) % MOD;
              right->mul = (right->mul * mul) % MOD;
              node->add = 0;
              node->mul = 1;
          }
      }
  };
  
  class Fancy {
  public:
      int n;
      SegmentTree* tree;
  
      Fancy() {
          n = 0;
          tree = new SegmentTree();
      }
  
      void append(int val) {
          ++n;
          tree->modifyAdd(n, n, val);
      }
  
      void addAll(int inc) {
          tree->modifyAdd(1, n, inc);
      }
  
      void multAll(int m) {
          tree->modifyMul(1, n, m);
      }
  
      int getIndex(int idx) {
          return idx >= n ? -1 : tree->query(idx + 1, idx + 1);
      }
  };
  
  /**
   * Your Fancy object will be instantiated and called as such:
   * Fancy* obj = new Fancy();
   * obj->append(val);
   * obj->addAll(inc);
   * obj->multAll(m);
   * int param_4 = obj->getIndex(idx);
   */
  
  
  // Solution 2
  class Fancy {
  public:
      void append(int val) {
          long long x = (val - b + mod) % mod * qpow(a, mod - 2) % mod;
          nums.push_back(x);
      }
  
      void addAll(int inc) {
          b = (b + inc) % mod;
      }
  
      void multAll(int m) {
          a = a * m % mod;
          b = b * m % mod;
      }
  
      int getIndex(int idx) {
          if (idx >= nums.size()) {
              return -1;
          }
          return (a * nums[idx] + b) % mod;
      }
  
  private:
      const int mod = 1e9 + 7;
      vector<long long> nums;
      long long a = 1, b = 0;
  
      long long qpow(long long x, int n) {
          long long res = 1;
          while (n) {
              if (n & 1) {
                  res = res * x % mod;
              }
              x = x * x % mod;
              n >>= 1;
          }
          return res;
      }
  };
  
  

• 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)
  
  
  
  # Solution 2
  class Fancy:
      def __init__(self):
          self.mod = 10**9 + 7
          self.nums = []
          self.a = 1
          self.b = 0
  
      def append(self, val: int) -> None:
          x = (val - self.b) * pow(self.a, self.mod - 2, self.mod) % self.mod
          self.nums.append(x)
  
      def addAll(self, inc: int) -> None:
          self.b = (self.b + inc) % self.mod
  
      def multAll(self, m: int) -> None:
          self.a = self.a * m % self.mod
          self.b = self.b * m % self.mod
  
      def getIndex(self, idx: int) -> int:
          if idx >= len(self.nums):
              return -1
          return (self.a * self.nums[idx] + self.b) % self.mod
  
  

• const MOD int64 = 1e9 + 7
  
  type Node struct {
  	left  *Node
  	right *Node
  	l     int
  	r     int
  	mid   int
  	v     int64
  	add   int64
  	mul   int64
  }
  
  func newNode(l, r int) *Node {
  	return &Node{
  		l:   l,
  		r:   r,
  		mid: (l + r) >> 1,
  		mul: 1,
  	}
  }
  
  type SegmentTree struct {
  	root *Node
  }
  
  func newSegmentTree() *SegmentTree {
  	return &SegmentTree{
  		root: newNode(1, 100001),
  	}
  }
  
  func (t *SegmentTree) modifyAdd(l, r int, inc int64) {
  	t.modifyAddNode(l, r, inc, t.root)
  }
  
  func (t *SegmentTree) modifyAddNode(l, r int, inc int64, node *Node) {
  	if l > r {
  		return
  	}
  
  	if node.l >= l && node.r <= r {
  		node.v = (node.v + int64(node.r-node.l+1)*inc) % MOD
  		node.add = (node.add + inc) % MOD
  		return
  	}
  
  	t.pushdown(node)
  
  	if l <= node.mid {
  		t.modifyAddNode(l, r, inc, node.left)
  	}
  
  	if r > node.mid {
  		t.modifyAddNode(l, r, inc, node.right)
  	}
  
  	t.pushup(node)
  }
  
  func (t *SegmentTree) modifyMul(l, r int, m int64) {
  	t.modifyMulNode(l, r, m, t.root)
  }
  
  func (t *SegmentTree) modifyMulNode(l, r int, m int64, node *Node) {
  	if l > r {
  		return
  	}
  
  	if node.l >= l && node.r <= r {
  		node.v = node.v * m % MOD
  		node.add = node.add * m % MOD
  		node.mul = node.mul * m % MOD
  		return
  	}
  
  	t.pushdown(node)
  
  	if l <= node.mid {
  		t.modifyMulNode(l, r, m, node.left)
  	}
  
  	if r > node.mid {
  		t.modifyMulNode(l, r, m, node.right)
  	}
  
  	t.pushup(node)
  }
  
  func (t *SegmentTree) query(l, r int) int {
  	return int(t.queryNode(l, r, t.root))
  }
  
  func (t *SegmentTree) queryNode(l, r int, node *Node) int64 {
  	if l > r {
  		return 0
  	}
  
  	if node.l >= l && node.r <= r {
  		return node.v
  	}
  
  	t.pushdown(node)
  
  	var v int64
  
  	if l <= node.mid {
  		v = (v + t.queryNode(l, r, node.left)) % MOD
  	}
  
  	if r > node.mid {
  		v = (v + t.queryNode(l, r, node.right)) % MOD
  	}
  
  	return v
  }
  
  func (t *SegmentTree) pushup(node *Node) {
  	node.v = (node.left.v + node.right.v) % MOD
  }
  
  func (t *SegmentTree) pushdown(node *Node) {
  
  	if node.left == nil {
  		node.left = newNode(node.l, node.mid)
  	}
  
  	if node.right == nil {
  		node.right = newNode(node.mid+1, node.r)
  	}
  
  	if node.add != 0 || node.mul != 1 {
  
  		add := node.add
  		mul := node.mul
  
  		left := node.left
  		right := node.right
  
  		left.v = (left.v*mul + int64(left.r-left.l+1)*add) % MOD
  		right.v = (right.v*mul + int64(right.r-right.l+1)*add) % MOD
  
  		left.add = (left.add*mul + add) % MOD
  		right.add = (right.add*mul + add) % MOD
  
  		left.mul = left.mul * mul % MOD
  		right.mul = right.mul * mul % MOD
  
  		node.add = 0
  		node.mul = 1
  	}
  }
  
  type Fancy struct {
  	n    int
  	tree *SegmentTree
  }
  
  func Constructor() Fancy {
  	return Fancy{
  		tree: newSegmentTree(),
  	}
  }
  
  func (f *Fancy) Append(val int) {
  	f.n++
  	f.tree.modifyAdd(f.n, f.n, int64(val))
  }
  
  func (f *Fancy) AddAll(inc int) {
  	f.tree.modifyAdd(1, f.n, int64(inc))
  }
  
  func (f *Fancy) MultAll(m int) {
  	f.tree.modifyMul(1, f.n, int64(m))
  }
  
  func (f *Fancy) GetIndex(idx int) int {
  	if idx >= f.n {
  		return -1
  	}
  	return f.tree.query(idx+1, idx+1)
  }
  
  
  
  // Solution 2
  const mod int = 1e9 + 7
  
  func qpow(x, n int) int {
  	res := 1
  	for n > 0 {
  		if n&1 == 1 {
  			res = res * x % mod
  		}
  		x = x * x % mod
  		n >>= 1
  	}
  	return res
  }
  
  type Fancy struct {
  	nums []int
  	a, b int
  }
  
  func Constructor() Fancy {
  	return Fancy{a: 1}
  }
  
  func (f *Fancy) Append(val int) {
  	x := (val - f.b + mod) % mod * qpow(f.a, mod-2) % mod
  	f.nums = append(f.nums, x)
  }
  
  func (f *Fancy) AddAll(inc int) {
  	f.b = (f.b + inc) % mod
  }
  
  func (f *Fancy) MultAll(m int) {
  	f.a = f.a * m % mod
  	f.b = f.b * m % mod
  }
  
  func (f *Fancy) GetIndex(idx int) int {
  	if idx >= len(f.nums) {
  		return -1
  	}
  	return (f.a*f.nums[idx] + f.b) % mod
  }
  
  

• const MOD = 1000000007n;
  
  class Node {
      left: Node | null = null;
      right: Node | null = null;
  
      l: number;
      r: number;
      mid: number;
  
      v = 0n;
      add = 0n;
      mul = 1n;
  
      constructor(l: number, r: number) {
          this.l = l;
          this.r = r;
          this.mid = (l + r) >> 1;
      }
  }
  
  class SegmentTree {
      root: Node;
  
      constructor() {
          this.root = new Node(1, 100001);
      }
  
      modifyAdd(l: number, r: number, inc: bigint, node: Node = this.root): void {
          if (l > r) return;
  
          if (node.l >= l && node.r <= r) {
              node.v = (node.v + BigInt(node.r - node.l + 1) * inc) % MOD;
              node.add = (node.add + inc) % MOD;
              return;
          }
  
          this.pushdown(node);
  
          if (l <= node.mid) this.modifyAdd(l, r, inc, node.left!);
          if (r > node.mid) this.modifyAdd(l, r, inc, node.right!);
  
          this.pushup(node);
      }
  
      modifyMul(l: number, r: number, m: bigint, node: Node = this.root): void {
          if (l > r) return;
  
          if (node.l >= l && node.r <= r) {
              node.v = (node.v * m) % MOD;
              node.add = (node.add * m) % MOD;
              node.mul = (node.mul * m) % MOD;
              return;
          }
  
          this.pushdown(node);
  
          if (l <= node.mid) this.modifyMul(l, r, m, node.left!);
          if (r > node.mid) this.modifyMul(l, r, m, node.right!);
  
          this.pushup(node);
      }
  
      query(l: number, r: number, node: Node = this.root): bigint {
          if (l > r) return 0n;
  
          if (node.l >= l && node.r <= r) return node.v;
  
          this.pushdown(node);
  
          let v = 0n;
  
          if (l <= node.mid) v = (v + this.query(l, r, node.left!)) % MOD;
          if (r > node.mid) v = (v + this.query(l, r, node.right!)) % MOD;
  
          return v;
      }
  
      pushup(node: Node): void {
          node.v = (node.left!.v + node.right!.v) % MOD;
      }
  
      pushdown(node: Node): void {
          if (!node.left) node.left = new Node(node.l, node.mid);
          if (!node.right) node.right = new Node(node.mid + 1, node.r);
  
          if (node.add !== 0n || node.mul !== 1n) {
              const add = node.add;
              const mul = node.mul;
  
              const left = node.left!;
              const right = node.right!;
  
              left.v = (left.v * mul + BigInt(left.r - left.l + 1) * add) % MOD;
              right.v = (right.v * mul + BigInt(right.r - right.l + 1) * add) % MOD;
  
              left.add = (left.add * mul + add) % MOD;
              right.add = (right.add * mul + add) % MOD;
  
              left.mul = (left.mul * mul) % MOD;
              right.mul = (right.mul * mul) % MOD;
  
              node.add = 0n;
              node.mul = 1n;
          }
      }
  }
  
  class Fancy {
      n = 0;
      tree = new SegmentTree();
  
      append(val: number): void {
          this.n++;
          this.tree.modifyAdd(this.n, this.n, BigInt(val));
      }
  
      addAll(inc: number): void {
          this.tree.modifyAdd(1, this.n, BigInt(inc));
      }
  
      multAll(m: number): void {
          this.tree.modifyMul(1, this.n, BigInt(m));
      }
  
      getIndex(idx: number): number {
          if (idx >= this.n) return -1;
          return Number(this.tree.query(idx + 1, idx + 1));
      }
  }
  
  /**
   * Your Fancy object will be instantiated and called as such:
   * var obj = new Fancy()
   * obj.append(val)
   * obj.addAll(inc)
   * obj.multAll(m)
   * var param_4 = obj.getIndex(idx)
   */
  
  
  
  // Solution 2
  class Fancy {
      private mod = BigInt(1e9 + 7);
      private nums: bigint[] = [];
      private a = 1n;
      private b = 0n;
  
      append(val: number): void {
          const x = (((BigInt(val) - this.b) % this.mod) + this.mod) % this.mod;
          this.nums.push((x * this.qpow(this.a, 1e9 + 5)) % this.mod);
      }
  
      addAll(inc: number): void {
          this.b = (this.b + BigInt(inc)) % this.mod;
      }
  
      multAll(m: number): void {
          this.a = (this.a * BigInt(m)) % this.mod;
          this.b = (this.b * BigInt(m)) % this.mod;
      }
  
      getIndex(idx: number): number {
          if (idx >= this.nums.length) {
              return -1;
          }
          return Number((this.a * this.nums[idx] + this.b) % this.mod);
      }
  
      private qpow(x: bigint, n: number): bigint {
          let res = 1n;
          while (n) {
              if (n & 1) {
                  res = (res * x) % this.mod;
              }
              x = (x * x) % this.mod;
              n >>= 1;
          }
          return res;
      }
  }
  
  

All Problems

All Solutions