Strange Strands

Author : Speedster1010

Required Knowledge : Segment Trees

Time Complexity : $\mathcal{O}((N + Q) \cdot \log N)$

Editorialist : Speedster1010

Approach:

This problem may look simple at first. The operations are straightforward, and even a naive approach seems easy to implement. However, the challenge arises when we must handle up to $Q$ update and query operations efficiently.

Specifically, we are asked to update characters in a string (consisting of lowercase English letters) and repeatedly find the length of the longest uniform substring. Performing a full scan of the string for every query would take $\mathcal{O}(N \cdot Q)$ time, which is too slow.

To solve this efficiently, we can use a segment tree, which allows both updates and queries in $\mathcal{O}(\log N)$ time. Each node of the tree stores information about a range, including:

$\bullet$ Longest uniform substring in the range (answer)

$\bullet$ Leftmost character

$\bullet$ Length of uniform prefix

$\bullet$ Rightmost character

$\bullet$ Length of uniform suffix

$\bullet$ Length of the range

The merge function combines two consecutive ranges as follows:

$1.$ The new range length = sum of both lengths.

$2.$ The new leftmost and rightmost characters come from the respective sides.

$3.$ The longest uniform substring is the maximum of both child answers, or the combined prefix + suffix length if the subsequent characters match.

$4.$ Prefix and suffix values are updated accordingly.

This design allows the segment tree to maintain all necessary information efficiently. Since each operation traverses only $\log N$ nodes, both updates and queries are fast enough for the given constraints.

Setter's Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Node {
    int ans;
    int pref, suff;
    char pref_char, suff_char;
    int len;
};
 
Node e() {
    return {0, 0, 0, '@', '@', 0};
}
 
Node make_leaf(char c) {
    return {1, 1, 1, c, c, 1};
}
 
int N;
string s;
vector<Node> seg;
 
Node merge(const Node& left, const Node& right) {
    if (left.len == 0) return right;
    if (right.len == 0) return left;
 
    Node res;
    res.len = left.len + right.len;
    res.pref_char = left.pref_char;
    res.suff_char = right.suff_char;
 
    res.ans = max(left.ans, right.ans);
    if (left.suff_char == right.pref_char) {
        res.ans = max(res.ans, left.suff + right.pref);
    }
 
    res.pref = left.pref;
    if (left.pref == left.len && left.suff_char == right.pref_char) {
        res.pref += right.pref;
    }
 
    res.suff = right.suff;
    if (right.suff == right.len && left.suff_char == right.pref_char) {
        res.suff += left.suff;
    }
    
    return res;
}
 
void update(int ind, int start, int end, int pos, Node val) {
    if(start == end) {
        seg[ind] = val;
        return;
    }
 
    int mid = (start + end) / 2;
    if(pos <= mid) {
        update(ind * 2, start, mid, pos, val);
    } else {
        update(ind * 2 + 1, mid + 1, end, pos, val);
    }
    seg[ind] = merge(seg[ind * 2], seg[ind * 2 + 1]);
};
 
void update(int pos, Node val) {
    update(1, 0, N - 1, pos, val);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int q;
    cin >> N >> q;
    cin >> s;
 
    seg.resize(4 * N);
    for(int i = 0; i < N; ++i) {
        update(i, make_leaf(s[i]));
    }
 
    for (int k = 0; k < q; ++k) {
        int type;
        cin >> type;
        if (type == 1) {
            int i;
            char c;
            cin >> i >> c;
            s[i - 1] = c;
            update(i - 1, make_leaf(s[i - 1]));
        } else {
            cout << seg[1].ans << "\n";
        }
    }
 
    return 0;
}