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

#include <set>
#include <map>
#include <vector>
#include <array>
#include <algorithm>
#include <iterator>

// Template class for managing intervals of type T with a size of N
template<typename T, int N>
class IntervalManager {
public:
    // Define an interval as an array of N elements of type T
    using Interval = std::array<T, N>;

    // Comparator to compare intervals based on their starting point
    struct Compare {
        bool operator()(const Interval& a, const Interval& b) const {
            return a[0] < b[0];
        }
    };

    // Set to store intervals, ordered by their starting points
    std::set<Interval, Compare> intervals;
    // Map to store frequencies of interval lengths
    std::map<T, int> lengthFrequencies;

    // Update the frequency of a given length by a specified delta
    void updateLengthFrequency(T length, int delta) {
        lengthFrequencies[length] += delta;
        if (lengthFrequencies[length] <= 0) {
            lengthFrequencies.erase(length);
        }
    }

    // Add an interval to the set and update the length frequencies
    void addInterval(const Interval& interval) {
        intervals.insert(interval);
        updateLengthFrequency(interval[1] - interval[0] + 1, 1);
    }

    // Remove an interval from the set and update the length frequencies
    void removeInterval(const Interval& interval) {
        intervals.erase(interval);
        updateLengthFrequency(interval[1] - interval[0] + 1, -1);
    }

    // Split an interval at a given index and insert a new interval with a new value
    typename std::set<Interval, Compare>::iterator splitInterval(T index, const Interval& interval, const T& newValue) {
        removeInterval(interval);
        if (interval[0] < index) {
            addInterval({interval[0], index - 1, interval[2]});
        }
        if (interval[1] > index) {
            addInterval({index + 1, interval[1], interval[2]});
        }
        updateLengthFrequency(1, 1);
        auto result = intervals.insert({index, index, newValue});
        return result.first;
    }

    // Merge an interval with its neighboring intervals if they have the same value
    template<class Iterator>
    void mergeIntervals(Iterator it) {
        Interval current = *it;
        Interval left = *std::prev(it);
        Interval right = *std::next(it);

        removeInterval(current);
        T newLeft = current[0], newRight = current[1];

        if (left[2] == current[2]) {
            removeInterval(left);
            newLeft = left[0];
        }
        if (current[2] == right[2]) {
            removeInterval(right);
            newRight = right[1];
        }
        addInterval({newLeft, newRight, current[2]});
    }

    // Update the value of an interval at a given index
    void updateInterval(T index, const T& newValue) {
        auto it = intervals.lower_bound({index, index, T()});
        Interval current = *it;
        if (current[0] > index) {
            current = *(--it);
        }
        if (newValue == current[2]) return;

        it = splitInterval(index, current, newValue);
        mergeIntervals(it);
    }

    // Process a series of queries on the data
    std::vector<T> processQueries(const std::string data, const std::string queryChars, const std::vector<int>& queryIndices) {
        int dataSize = data.size();
        int querySize = queryChars.size();
        std::vector<T> augmentedData = {T()};
        augmentedData.insert(augmentedData.end(), data.begin(), data.end());
        augmentedData.push_back(T());
        
        int start = 1;
        T previousValue = augmentedData[1];

        addInterval({0, 0, T()});
        addInterval({dataSize + 1, dataSize + 1, T()});
        
        for (int i = 2; i <= dataSize + 1; ++i) {
            if (augmentedData[i] == previousValue) continue;
            addInterval({start, i - 1, previousValue});
            previousValue = augmentedData[i];
            start = i;
        }

        std::vector<T> result(querySize);
        for (int i = 0; i < querySize; ++i) {
            updateInterval(queryIndices[i] + 1, queryChars[i]);
            result[i] = lengthFrequencies.rbegin()->first;
        }
        return result;
    }
};

// Example usage of IntervalManager in the context of a solution class
class Solution {
public:
    std::vector<int> longestRepeating(std::string S, std::string qc, std::vector<int>& qi) {
        IntervalManager<int, 3> manager;
        return manager.processQueries(S, qc, qi);
    }
};

189400