3777. Minimum Deletions to Make Alternating Substring

You are given a string s of length n consisting only of the characters 'A' and 'B'.

You are also given a 2D integer array queries of length q, where each queries[i] is one of the following:

• [1, j]: Flip the character at index j of s i.e. 'A' changes to 'B' (and vice versa). This operation mutates s and affects subsequent queries.
• [2, l, r]: Compute the minimum number of character deletions required to make the substring s[l..r] alternating. This operation does not modify s; the length of s remains n.

A substring is alternating if no two adjacent characters are equal. A substring of length 1 is always alternating.

Return an integer array answer, where answer[i] is the result of the i^th query of type [2, l, r].

struct Seg {
    int mi,ma;
    int head,tail,cnt;
    Seg *left, *right;

    Seg(string& s, int l, int r) : mi(l), ma(r), head(s[l] == 'A'), tail(s[r] == 'A'), cnt(0), left(nullptr), right(nullptr) {
        if(l^r) {
            int m = l + (r - l) / 2;
            left = new Seg(s,l,m);
            right = new Seg(s,m+1,r);
            cnt = left->cnt + right->cnt + (left->tail == right->head);
        }
    }
    void update(int n, int x) {
        if(mi <= n and n <= ma) {
            if(mi == n and n == ma) {
                head = tail = x;
                return;
            }
            left->update(n,x);
            right->update(n,x);
            head = left->head, tail = right->tail;
            cnt = left->cnt + right->cnt + (left->tail == right->head);
        }
    }
    array<int,3> query(int l, int r) {
        if(l <= mi and ma <= r) return {head,tail,cnt};
        if(l > ma or r < mi) return {-1,-1,0};
        auto [leHead, leTail, leCnt] = left->query(l,r);
        auto [riHead, riTail, riCnt] = right->query(l,r);
        if(leHead == -1) return {riHead, riTail, riCnt};
        if(riHead == -1) return {leHead, leTail, leCnt};
        int now = leCnt + riCnt + (leTail == riHead);
        return {leHead, riTail, now};
    }
};

class Solution {
public:
    vector<int> minDeletions(string s, vector<vector<int>>& queries) {
        Seg* seg = new Seg(s,0,s.length() - 1);
        vector<int> res;
        for(auto& q : queries) {
            int op = q[0];
            if(op == 1) {
                int idx = q[1];
                s[idx] = s[idx] == 'A' ? 'B' : 'A';
                seg->update(idx,s[idx] == 'A');
            } else {
                int l = q[1], r = q[2];
                auto [head,tail,sum] = seg->query(l,r);
                assert(head != -1);
                assert(tail != -1);
                res.push_back(sum);
            }
        }
        return res;
    }
};