<p>Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array <code>fruits</code> where <code>fruits[i] = [position<sub>i</sub>, amount<sub>i</sub>]</code> depicts <code>amount<sub>i</sub></code> fruits at the position <code>position<sub>i</sub></code>. <code>fruits</code> is already <strong>sorted</strong> by <code>position<sub>i</sub></code> in <strong>ascending order</strong>, and each <code>position<sub>i</sub></code> is <strong>unique</strong>.</p>

<p>You are also given an integer <code>startPos</code> and an integer <code>k</code>. Initially, you are at the position <code>startPos</code>. From any position, you can either walk to the <strong>left or right</strong>. It takes <strong>one step</strong> to move <strong>one unit</strong> on the x-axis, and you can walk <strong>at most</strong> <code>k</code> steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.</p>

<p>Return <em>the <strong>maximum total number</strong> of fruits you can harvest</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/1.png" style="width: 472px; height: 115px;" />
<pre>
<strong>Input:</strong> fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
<strong>Output:</strong> 9
<strong>Explanation:</strong> 
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/2.png" style="width: 512px; height: 129px;" />
<pre>
<strong>Input:</strong> fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
<strong>Output:</strong> 14
<strong>Explanation:</strong> 
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/3.png" style="width: 476px; height: 100px;" />
<pre>
<strong>Input:</strong> fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong>
You can move at most k = 2 steps and cannot reach any position with fruits.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= fruits.length &lt;= 10<sup>5</sup></code></li>
	<li><code>fruits[i].length == 2</code></li>
	<li><code>0 &lt;= startPos, position<sub>i</sub> &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>position<sub>i-1</sub> &lt; position<sub>i</sub></code> for any <code>i &gt; 0</code>&nbsp;(<strong>0-indexed</strong>)</li>
	<li><code>1 &lt;= amount<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= k &lt;= 2 * 10<sup>5</sup></code></li>
</ul>

class TreeNode:
  def __init__(self, start, end, amount, left=None, right=None):
    self.start = start
    self.end = end
    self.left = left
    self.right = right
    self.amount = amount

  def makeParent(a, b):
    parent = TreeNode(start=a.start, end=b.end, amount=a.amount+b.amount, left=a, right=b,)
    return parent

  def search(self, start, end):
    if start<=self.start and self.end<=end:
      # node is in target
      return (self.start, self.end)
    if self.end<start or end<self.start:
      # node is out of target
      return (-1, -1)
    left = self.left.search(start, end)
    right = self.right.search(start, end)
    if left == (-1,-1):
      return right
    if right == (-1,-1):
      return left
    return (left[0] if left[0]!=-1 else left[1], right[1] if right[1]!=-1 else right[0])

  def getAmount(self, start, end):
    if start<=self.start and self.end<=end:
      # node is in target
      return self.amount
    if self.end<start or end<self.start:
      # node is out of target
      return 0
    left = self.left.getAmount(start, end)
    right = self.right.getAmount(start, end)
    return left + right

class Solution:
  def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
    poss = list()
    nodes = list()
    for p,a in fruits:
      if startPos-k<=p and p<=startPos+k:
        nodes.append(TreeNode(start=p, end=p, amount=a))
        poss.append(p)
    poss.sort()
    if not nodes:return 0
    while(len(nodes)>1):
      next_nodes = list()
      while(len(nodes)>1):
        next_nodes.append(TreeNode.makeParent(nodes.pop(0),nodes.pop(0)))
      if len(nodes)==1:
        next_nodes.append(TreeNode.makeParent(next_nodes.pop(-1),nodes.pop(0)))
      nodes = next_nodes
    root_node = nodes[0]

    max_num = 0

    n=root_node.getAmount(startPos-k, startPos)
    max_num = max(n, max_num)

    start, end = root_node.search(startPos-k/2,startPos)
    if start!=-1:
      for turningPos in poss[poss.index(start):poss.index(end)+1]:
        endPos = k-startPos+2*turningPos
        n=root_node.getAmount(turningPos, endPos)
        max_num = max(n, max_num)
    start, end = root_node.search(startPos,startPos+k/2)
    if start!=-1:
      for turningPos in poss[poss.index(start):poss.index(end)+1]:
        remain_distance = k-2*(turningPos-startPos)
        endPos = startPos - remain_distance
        n=root_node.getAmount(endPos, turningPos)
        max_num = max(n, max_num)
    
    n=root_node.getAmount(startPos, startPos+k)
    max_num = max(n, max_num)

    return max_num
63700