<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>


class SegTree
{
public:
  SegTree(int n, string& str)
  {
    s = str;
    cap = n;
    data.assign(4 * n + 1, vector<int64_t>(8, 0));
    for (int i = 0; i < 4 * n + 1; ++i)
      {
	    data[i][0] = -1;
	    data[i][1] = -1;
	    data[i][2] = 0; // left character
        data[i][3] = 0; // left#
        data[i][4] = 0; // right character
        data[i][5] = 0; // right#
        data[i][6] = 0;
        data[i][7] = 0;
      }
    build(1, 0, n - 1);    
  }

  void Update(int pos, int delta)
  {
    //update(1, pos, pos, delta);
  }

  int64_t Query(int lo, int hi)
  {
    //return query(1, lo, hi);
    return 0;
  }

  void build(int index, int lo, int hi)
  {
    if (lo > hi) return;
    data[index][0] = lo;
    data[index][1] = hi;
    if (lo == hi)
      {
	    data[index][2] = s[lo] - 'a'; // left character
        data[index][3] = 1; // left# 
        data[index][4] = s[lo] - 'a'; // right character
        data[index][5] = 1; // right#
        data[index][6] = s[lo] - 'a'; // max length character        
        data[index][7] = 1; // max length       
	    return;
      }

    build(2 * index, lo, lo + (hi - lo) / 2);
    build(2 * index + 1, lo + (hi - lo)/2 + 1, hi);
    updateParent(index);
  }

  void updateParent(int index)
  {
    data[index][2] = 0;    
    data[index][3] = 0;
    data[index][4] = 0;
    data[index][5] = 0;
    data[index][6] = 0;
    data[index][7] = 0;

    //cout << "Update," << data[index][0] << " ~ " << data[index][1] << endl;
    if (data[index * 2][0] != -1) 
    {        
      //  cout << "left," <<  data[index * 2][0] << "," << data[index * 2][1] << "|"
     //        << char(data[index * 2][4] + 'a') << "," << data[index * 2][5] << endl;
        data[index][2] = data[index * 2][2];
        data[index][3] = data[index * 2][3];            
        if (data[index * 2][7] > data[index][7]) 
        {
            data[index][6] = data[index * 2][6];
            data[index][7] = data[index * 2][7];
        }
    }
    if (data[index * 2 + 1][1] != -1) 
    {
       // cout << "right," <<  data[index * 2 + 1][0] << "," << data[index * 2 + 1][1] << "|"
       //      << char(data[index * 2 + 1][2] + 'a') << "," << data[index * 2 + 1][3] << endl;
        data[index][4] = data[index * 2 + 1][4];
        data[index][5] = data[index * 2 + 1][5];    
        if (data[index * 2 + 1][7] > data[index][7]) 
        {
            data[index][6] = data[index * 2 + 1][6];
            data[index][7] = data[index * 2 + 1][7];
        }            
    }
    if (data[index * 2][0] != -1 && data[index * 2 + 1][1] != -1)
    {
        int leftLen = data[index * 2][1] - data[index * 2][0] + 1;
        if (leftLen == data[index * 2][3] && data[index * 2][2] == data[index * 2 + 1][2])
        {
            data[index][3] += data[index * 2 + 1][3];
        }
       // cout << "left,len|" << leftLen << "," << data[index][3] << endl;
        int rightLen = data[index * 2 + 1][1] - data[index * 2 + 1][0] + 1;
        if (rightLen == data[index * 2 + 1][5] && data[index * 2][4] == data[index * 2 + 1][4])
        {
            data[index][5] += data[index * 2][5];
        }
      //  cout << "right,len|" << rightLen << "," << data[index][5] << endl;

        if (data[index * 2][4] == data[index * 2 + 1][2])
        {
            int newLen = data[index * 2][5] + data[index * 2 + 1][3];
            if (newLen > data[index][7])
            {
                data[index][6] = data[index * 2][2];
                data[index][7] = newLen;
            }
        }
    }

    if (data[index][3] > data[index][7])
    {
        data[index][6] = data[index][2];
        data[index][7] = data[index][3];
    }

    if (data[index][5] > data[index][7])
    {
        data[index][6] = data[index][4];
        data[index][7] = data[index][5];
    }

    // cout << "Update, Finish," 
    //      << data[index][0] << " ~ " << data[index][1] << "|"
    //      << char('a' + data[index][6]) << "," << data[index][7] 
     //     << endl;
  }

  void Update(int index, char c)
  {
    update(1, index, index, c - 'a');
  }

  void update(int index, int lo, int hi, int val)
  {
    if (lo > hi) return;
    if (data[index][0] > hi || data[index][1] < lo) return;
    if (data[index][0] == data[index][1])
    {                
      //  cout << "UpdateValue," 
      //       << data[index][0] << "," << data[index][1] << "," << char('a' + val)
      //       << endl;
      data[index][2] = val; // left character
      data[index][3] = 1; // left# 
      data[index][4] = val; // right character
      data[index][5] = 1; // right#
      data[index][6] = val; // max length character        
      data[index][7] = 1; // max length  
      return;
    }
    if (data[2 * index][0] != -1) update(2 * index, lo, hi, val);
    if (data[2 * index + 1][0] != -1) update(2 * index + 1, lo, hi, val);
    updateParent(index);
  }

  int Query()
  {
    return data[1][7];
  }

  string s;
  int cap;
  vector< vector<int64_t> > data;
};

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

        SegTree st(s.size(), s);    
       // cout << "---------------------------" << endl;
        for (int i = 0; i < queryCharacters.size(); ++i)
        {
            st.Update(queryIndices[i], queryCharacters[i]);
            ans.push_back(st.Query());
        }

        return ans;
    }
};
347900