<p>You are given a <strong>0-indexed</strong> string <code>s</code>. You are also given a <strong>0-indexed</strong> string <code>queryCharacters</code> of length <code>k</code> and a <strong>0-indexed</strong> array of integer <strong>indices</strong> <code>queryIndices</code> of length <code>k</code>, both of which are used to describe <code>k</code> queries.</p>

<p>The <code>i<sup>th</sup></code> query updates the character in <code>s</code> at index <code>queryIndices[i]</code> to the character <code>queryCharacters[i]</code>.</p>

<p>Return <em>an array</em> <code>lengths</code> <em>of length </em><code>k</code><em> where</em> <code>lengths[i]</code> <em>is the <strong>length</strong> of the <strong>longest substring</strong> of </em><code>s</code><em> consisting of <strong>only one repeating</strong> character <strong>after</strong> the</em> <code>i<sup>th</sup></code> <em>query</em><em> is performed.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babacc&quot;, queryCharacters = &quot;bcb&quot;, queryIndices = [1,3,3]
<strong>Output:</strong> [3,3,4]
<strong>Explanation:</strong> 
- 1<sup>st</sup> query updates s = &quot;<u>b<strong>b</strong>b</u>acc&quot;. The longest substring consisting of one repeating character is &quot;bbb&quot; with length 3.
- 2<sup>nd</sup> query updates s = &quot;bbb<u><strong>c</strong>cc</u>&quot;. 
  The longest substring consisting of one repeating character can be &quot;bbb&quot; or &quot;ccc&quot; with length 3.
- 3<sup>rd</sup> query updates s = &quot;<u>bbb<strong>b</strong></u>cc&quot;. The longest substring consisting of one repeating character is &quot;bbbb&quot; with length 4.
Thus, we return [3,3,4].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abyzz&quot;, queryCharacters = &quot;aa&quot;, queryIndices = [2,1]
<strong>Output:</strong> [2,3]
<strong>Explanation:</strong>
- 1<sup>st</sup> query updates s = &quot;ab<strong>a</strong><u>zz</u>&quot;. The longest substring consisting of one repeating character is &quot;zz&quot; with length 2.
- 2<sup>nd</sup> query updates s = &quot;<u>a<strong>a</strong>a</u>zz&quot;. The longest substring consisting of one repeating character is &quot;aaa&quot; with length 3.
Thus, we return [2,3].
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
	<li><code>k == queryCharacters.length == queryIndices.length</code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
	<li><code>queryCharacters</code> consists of lowercase English letters.</li>
	<li><code>0 &lt;= queryIndices[i] &lt; s.length</code></li>
</ul>

struct SegmentTreeNode {
  int lo;
  int hi;
  char maxLetter;
  char prefixLetter;
  char suffixLetter;
  int maxLength;
  int prefixLength;
  int suffixLength;
  SegmentTreeNode* left;
  SegmentTreeNode* right;
  SegmentTreeNode(int lo, int hi, char maxLetter, char prefixLetter,
                  char suffixLetter, int maxLength, int prefixLength,
                  int suffixLength, SegmentTreeNode* left = nullptr,
                  SegmentTreeNode* right = nullptr)
      : lo(lo),
        hi(hi),
        maxLetter(maxLetter),
        prefixLetter(prefixLetter),
        suffixLetter(suffixLetter),
        maxLength(maxLength),
        prefixLength(prefixLength),
        suffixLength(suffixLength),
        left(left),
        right(right) {}
  ~SegmentTreeNode() {
    delete left;
    delete right;
    left = nullptr;
    right = nullptr;
  }
};

class SegmentTree {
 public:
  explicit SegmentTree(const string& s) : root(build(s, 0, s.length() - 1)) {}
  ~SegmentTree() {
    delete root;
  }

  void update(int i, char val) {
    root = update(root, i, val);
  }

  int getMaxLength() {
    return root->maxLength;
  }

 private:
  SegmentTreeNode* root;

  SegmentTreeNode* build(const string& s, int lo, int hi) const {
    if (lo == hi)
      return new SegmentTreeNode(lo, hi, s[lo], s[lo], s[lo], 1, 1, 1);
    const int mid = (lo + hi) / 2;
    SegmentTreeNode* left = build(s, lo, mid);
    SegmentTreeNode* right = build(s, mid + 1, hi);
    return merge(left, right);
  }

  SegmentTreeNode* update(SegmentTreeNode* root, int i, char c) {
    if (root->lo == i && root->hi == i) {
      root->maxLetter = c;
      root->prefixLetter = c;
      root->suffixLetter = c;
      return root;
    }
    const int mid = (root->lo + root->hi) / 2;
    if (i <= mid) {
      SegmentTreeNode* updatedLeft = update(root->left, i, c);
      return root = merge(updatedLeft, root->right);
    } else {
      SegmentTreeNode* updatedRight = update(root->right, i, c);
      return root = merge(root->left, updatedRight);
    }
  }

  SegmentTreeNode* merge(SegmentTreeNode* left, SegmentTreeNode* right) const {
    // Get `maxLetter` and `maxLength`.
    char maxLetter = ' ';
    int maxLength = 0;
    if (left->maxLength > right->maxLength) {
      maxLetter = left->maxLetter;
      maxLength = left->maxLength;
    } else {
      maxLetter = right->maxLetter;
      maxLength = right->maxLength;
    }
    if (left->suffixLetter == right->prefixLetter &&
        left->suffixLength + right->prefixLength > maxLength) {
      maxLetter = left->suffixLetter;
      maxLength = left->suffixLength + right->prefixLength;
    }

    // Get `prefixLetter` and `prefixLength`.
    char prefixLetter = left->prefixLetter;
    int prefixLength = left->prefixLength;
    if (left->lo + prefixLength == right->lo &&
        left->prefixLetter == right->prefixLetter)
      prefixLength += right->prefixLength;

    // Get `suffixLetter` and `suffixLength`.
    char suffixLetter = right->suffixLetter;
    int suffixLength = right->suffixLength;
    if (right->hi - suffixLength == left->hi &&
        right->suffixLetter == left->suffixLetter)
      suffixLength += left->suffixLength;
    return new SegmentTreeNode(left->lo, right->hi, maxLetter, prefixLetter,
                               suffixLetter, maxLength, prefixLength,
                               suffixLength, left, right);
  }
};

class Solution {
 public:
  vector<int> longestRepeating(string s, string queryLetteracters,
                               vector<int>& queryIndices) {
    vector<int> ans;
    SegmentTree tree(s);

    for (int i = 0; i < queryIndices.size(); ++i) {
      tree.update(queryIndices[i], queryLetteracters[i]);
      ans.push_back(tree.getMaxLength());
    }

    return ans;
  }
};
674600