ABC415F 题解

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 500010; 

struct Node {
    char l, r;      
    int lx, rx, mx; 
    int sz;         
} T[maxn * 4];        

char s[maxn];              

Node merge(Node a, Node b) {
    if (!a.sz) return b; 
    if (!b.sz) return a; 
    Node c;
    c.sz = a.sz + b.sz;
    c.l = a.l;
    c.r = b.r;
    
    c.lx = a.lx;
    if (a.lx == a.sz && a.r == b.l) 
        c.lx = a.sz + b.lx;
    
    c.rx = b.rx;
    if (b.rx == b.sz && a.r == b.l) 
        c.rx = b.sz + a.rx;
    
    c.mx = max(a.mx, b.mx);
    if (a.r == b.l) 
        c.mx = max(c.mx, a.rx + b.lx);
    
    return c;
}

void build(int l, int r, int i) {
    if (l == r) {
        T[i] = {s[l], s[l], 1, 1, 1, 1};
        return;
    }
    int m = (l + r) / 2;
    build(l, m, i << 1);
    build(m + 1, r, i << 1 | 1);
    T[i] = merge(T[i << 1], T[i << 1 | 1]);
}

void update(int p, char x, int l, int r, int i) {
    if (l == r) {
        T[i] = {x, x, 1, 1, 1, 1};
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, x, l, m, i << 1);
    else update(p, x, m + 1, r, i << 1 | 1);
    T[i] = merge(T[i << 1], T[i << 1 | 1]);
}

Node query(int l, int r, int s, int e, int i) {
    if (e < l || r < s) return Node{0, 0, 0, 0, 0, 0}; 
    if (s <= l && r <= e) return T[i];
    int m = (l + r) / 2;
    Node a = query(l, m, s, e, i << 1);
    Node b = query(m + 1, r, s, e, i << 1 | 1);
    return merge(a, b);
}

inline int read() {
    int x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}

signed main() {
    int n = read(),q = read();
    for (int i = 1; i <= n; i++) s[i] = getchar();
    build(1, n, 1);
    while (q--) {
        int op = read();
        if (op == 1) {
            int p = read();
            char x = getchar();
            update(p, x, 1, n, 1);
        } else {
            int l = read(), r = read();
            Node res = query(1, n, l, r, 1);
            cout << res.mx << "\n";
        }
    }
    return 0;
}