<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 cell {
  int Fst = -1;
  int Lst = -1;
  int L = -1;
  int R = -1;
  int M = -1;
  int Len = -1;
  cell () {}
  void _init (int Fst, int Lst, int L, int R, int M, int Len) {
    this -> Fst = Fst;
    this -> Lst = Lst;
    this -> L = L;
    this -> R = R;
    this -> M = M;
    this -> Len = Len;
  }
};

cell Merge(cell A, cell B) {
  if (A.L == -1) return B;
  cell Res;
  Res.Fst = A.Fst;
  Res.Lst = B.Lst;
  Res.M = max({A.M, B.M, (A.Lst == B.Fst ? A.R + B.L : 0)});
  Res.L = max({A.L, (A.Fst == B.Fst && A.L == A.Len ? A.L + B.L : 0)});
  Res.R = max({B.R, (B.Lst == A.Lst && B.R == B.Len ? B.R + A.R : 0)});
  Res.Len = A.Len + B.Len;
  return Res;
}

struct Node {
  Node* lft = NULL;
  Node* rht = NULL;
  cell V;
  int l, r;
  Node(int l, int r) {
    this -> l = l;
    this -> r = r;
  }
  void extend() {
    if (!lft && l + 1 <= r) {
      int mid = (l + r) >> 1;
      lft = new Node(l, mid);
      rht = new Node(mid + 1, r);
    }
  }
  void put(int i, int x) {
    if (l == r) {
      V._init(x, x, 1, 1, 1, 1);
      return;
    }
    extend();
    int mid = (l + r) >> 1;
    if (i <= mid) lft -> put(i, x);
    else rht -> put(i, x);
    V = Merge(lft -> V, rht -> V);
  }
  cell qry(int L, int R) {
    if (l >= L && r <= R) 
      return V;
    extend();
    int mid = (l + r) >> 1;
    cell res;
    if (L <= mid) res = Merge(res, lft -> qry(L, R));
    if (R >= mid + 1) res = Merge(res, rht -> qry(L, R));
    return res;
  }
};

class Solution {
public:
    vector<int> longestRepeating(string s, string qC, vector<int>& qI) {
      int N = s.size();
      int K = qI.size();
      Node* root = new Node(0, N - 1);
      for (int i = 0; i < N; ++i) {
        root -> put(i, (int) s[i] - 'a');
      }

      vector <int> Res (K);
      for (int i = 0; i < K; ++i) {
        root -> put(qI[i], (int) qC[i] - 'a');
        Res[i] = (root -> qry(0, N - 1)).M;
      }
      return Res;
    }
};
136100