提出 #67727899

---

ソースコード 拡げる

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

struct Node {
    char leftChar, rightChar;
    int length;
    int leftCnt, rightCnt, bestCnt;
    Node() {
        leftChar = rightChar = 0;
        length = leftCnt = rightCnt = bestCnt = 0;
    }
    Node(char c) {
        leftChar = rightChar = c;
        length = leftCnt = rightCnt = bestCnt = 1;
    }
};

class Solution {
    int N, Q;
    string S;
    Node *tree;

    Node combine(Node &L, Node &R) {
        if (L.length == 0) return R;
        if (R.length == 0) return L;
        Node res;
        res.length = L.length + R.length;
        res.leftChar = L.leftChar;
        res.rightChar = R.rightChar;

        res.bestCnt = max(L.bestCnt, R.bestCnt);
        if (L.rightChar == R.leftChar) {
            int cross = L.rightCnt + R.leftCnt;
            res.bestCnt = max(res.bestCnt, cross);
        }

        res.leftCnt = L.leftCnt;
        if (L.leftCnt == L.length && L.rightChar == R.leftChar) {
            res.leftCnt = L.length + R.leftCnt;
        }

        res.rightCnt = R.rightCnt;
        if (R.rightCnt == R.length && L.rightChar == R.leftChar) {
            res.rightCnt = R.length + L.rightCnt;
        }

        return res;
    }

    void build(int idx, int l, int r) {
        if (l == r) {
            tree[idx] = Node(S[l]);
            return;
        }
        int mid = (l + r) / 2;
        build(idx*2, l, mid);
        build(idx*2+1, mid+1, r);
        tree[idx] = combine(tree[idx*2], tree[idx*2+1]);
    }

    void update(int idx, int l, int r, int pos, char c) {
        if (l == r) {
            tree[idx] = Node(c);
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(idx*2, l, mid, pos, c);
        } else {
            update(idx*2+1, mid+1, r, pos, c);
        }
        tree[idx] = combine(tree[idx*2], tree[idx*2+1]);
    }

    Node query(int idx, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) {
            return Node();
        }
        if (ql <= l && r <= qr) {
            return tree[idx];
        }
        int mid = (l + r) / 2;
        Node leftRes = query(idx*2, l, mid, ql, qr);
        Node rightRes = query(idx*2+1, mid+1, r, ql, qr);
        return combine(leftRes, rightRes);
    }

public:
    void solve() {
        cin >> N >> Q;
        cin >> S;
        tree = new Node[4 * N + 5];

        build(1, 0, N - 1);

        for (int qi = 0; qi < Q; ++qi) {
            int type;
            cin >> type;
            if (type == 1) {
                int pos;
                char c;
                cin >> pos >> c;
                --pos;
                update(1, 0, N - 1, pos, c);
            } else {
                int l, r;
                cin >> l >> r;
                --l; --r;
                Node ans = query(1, 0, N - 1, l, r);
                cout << ans.bestCnt << "\n";
            }
        }

    }
};

int main() {
    Solution *sol = new Solution();
    sol->solve();
    return 0;
}

提出情報

ジャッジ結果