【综合笔试题】难度 4/5，字符处理的线段树经典运用

输入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]

输出：[3,3,4]

解释：
- 第 1 次查询更新后 s = "bbbacc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。
- 第 2 次查询更新后 s = "bbbccc" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。
- 第 3 次查询更新后 s = "bbbbcc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。
因此，返回 [3,3,4] 。

输入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]

输出：[2,3]

解释：
- 第 1 次查询更新后 s = "abazz" 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。
- 第 2 次查询更新后 s = "aaazz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。
因此，返回 [2,3] 。

class Solution {
    class Node {
        int l, r, prefix, suffix, val;
        Node(int _l, int _r) {
            l = _l; r = _r;
            prefix = suffix = val = 1;
        }
    }
    char[] cs;
    Node[] tr;
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l == r) return ;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int x, char c) {
        if (tr[u].l == x && tr[u].r == x) {
            cs[x - 1] = c;
            return ;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) update(u << 1, x, c);
        else update(u << 1 | 1, x, c);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int ans = 0;
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) ans = query(u << 1, l, r);
        if (r > mid) ans = Math.max(ans, query(u << 1 | 1, l, r));
        return ans;
    }
    void pushup(int u) {
        Node left = tr[u << 1], right = tr[u << 1 | 1];
        int aLen = left.r - left.l + 1, bLen = right.r - right.l + 1;
        char ac = cs[left.r - 1], bc = cs[right.l - 1];
        tr[u].prefix = left.prefix; tr[u].suffix = right.suffix;
        tr[u].val = Math.max(left.val, right.val);
        if (ac == bc) {
            if (left.prefix == aLen) tr[u].prefix = aLen + right.prefix;
            if (right.prefix == bLen) tr[u].suffix = bLen + left.suffix;
            tr[u].val = Math.max(tr[u].val, left.suffix + right.prefix);
        } 
    }
    public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
        cs = s.toCharArray();
        int n = cs.length, m = queryCharacters.length();
        tr = new Node[n * 4];
        build(1, 1, n);
        for (int i = 0; i < n; i++) update(1, i + 1, cs[i]);
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            update(1, queryIndices[i] + 1, queryCharacters.charAt(i));
            ans[i] = query(1, 1, n);
        }
        return ans;
    }
}