1/**
2 * A Binary Indexed Tree (Fenwick Tree) that supports point updates
3 * and prefix-sum queries in O(log n) time.
4 */
5class BinaryIndexedTree {
6    // Size of the underlying logical array.
7    private int size;
8    // Internal tree storage; indices are 1-based.
9    private int[] tree;
10
11    /**
12     * Constructs a Binary Indexed Tree for an array of the given length.
13     *
14     * @param size the number of elements the tree should support
15     */
16    BinaryIndexedTree(int size) {
17        this.size = size;
18        this.tree = new int[size + 1];
19    }
20
21    /**
22     * Adds {@code delta} to the element at position {@code index} (1-based).
23     *
24     * @param index the 1-based position to update
25     * @param delta the value to add at that position
26     */
27    void update(int index, int delta) {
28        // Walk upward, updating every responsible node by adding the lowbit.
29        while (index <= size) {
30            tree[index] += delta;
31            index += index & -index;
32        }
33    }
34
35    /**
36     * Returns the prefix sum of the first {@code index} elements (1-based).
37     *
38     * @param index the 1-based right boundary (inclusive) of the prefix
39     * @return the sum of elements in the range [1, index]
40     */
41    int query(int index) {
42        int sum = 0;
43        // Walk downward, accumulating partial sums by removing the lowbit.
44        while (index > 0) {
45            sum += tree[index];
46            index -= index & -index;
47        }
48        return sum;
49    }
50}
51
52class Solution {
53    /**
54     * Processes a list of queries over a binary string.
55     *
56     * <p>For each character at position {@code i} (i >= 1), {@code marks[i]} is 1
57     * when {@code s[i] == s[i - 1]} (i.e., this position forms an "equal-adjacent"
58     * pair with its predecessor). The Binary Indexed Tree stores these marks so
59     * that range counts of such pairs can be answered quickly.</p>
60     *
61     * <p>Query types:</p>
62     * <ul>
63     *   <li>{@code [1, j]} — toggle character at index {@code j}, refreshing the
64     *       affected adjacency marks at positions {@code j} and {@code j + 1}.</li>
65     *   <li>{@code [2, l, r]} — count the equal-adjacent pairs within [l, r],
66     *       which equals the minimum deletions needed to remove repeats.</li>
67     * </ul>
68     *
69     * @param s       the binary string
70     * @param queries the array of queries to process
71     * @return an array of answers, one per type-2 query, in order
72     */
73    public int[] minDeletions(String s, int[][] queries) {
74        int length = s.length();
75        // marks[i] == 1 means s[i] equals s[i - 1]; marks[0] is always 0.
76        int[] marks = new int[length];
77        BinaryIndexedTree bit = new BinaryIndexedTree(length);
78
79        // Initialize the adjacency marks and seed the tree accordingly.
80        for (int i = 1; i < length; i++) {
81            marks[i] = (s.charAt(i) == s.charAt(i - 1)) ? 1 : 0;
82            if (marks[i] == 1) {
83                bit.update(i + 1, 1);
84            }
85        }
86
87        // Pre-count how many type-2 queries exist to size the answer array.
88        int answerCount = 0;
89        for (int[] query : queries) {
90            if (query[0] == 2) {
91                answerCount++;
92            }
93        }
94
95        int[] answers = new int[answerCount];
96        int answerIndex = 0;
97
98        // Note: toggling a character does not change the actual mark values used
99        // in the original logic; the code flips marks and applies the delta so the
100        // tree stays consistent with the maintained marks array.
101        for (int[] query : queries) {
102            if (query[0] == 1) {
103                int position = query[1];
104
105                // Flip the mark at this position and reflect the change in the tree.
106                int delta = (marks[position] ^ 1) - marks[position];
107                marks[position] ^= 1;
108                bit.update(position + 1, delta);
109
110                // Flip the mark at the next position as it shares the adjacency.
111                if (position + 1 < length) {
112                    delta = (marks[position + 1] ^ 1) - marks[position + 1];
113                    marks[position + 1] ^= 1;
114                    bit.update(position + 2, delta);
115                }
116            } else {
117                int left = query[1];
118                int right = query[2];
119                // Count equal-adjacent pairs in (left, right] of the marks array.
120                answers[answerIndex++] = bit.query(right + 1) - bit.query(left + 1);
121            }
122        }
123        return answers;
124    }
125}
126

1class BinaryIndexedTree {
2public:
3    int size;                  // Total number of positions the tree manages
4    vector<int> tree;          // Internal Fenwick tree storage (1-indexed)
5
6    BinaryIndexedTree(int size)
7        : size(size)
8        , tree(size + 1, 0) {}
9
10    // Add `delta` to position `index` and propagate to affected nodes
11    void update(int index, int delta) {
12        while (index <= size) {
13            tree[index] += delta;
14            index += index & -index;   // Move to the next responsible node
15        }
16    }
17
18    // Return the prefix sum from position 1 up to `index` (inclusive)
19    int query(int index) {
20        int sum = 0;
21        while (index > 0) {
22            sum += tree[index];
23            index -= index & -index;   // Move to the parent node
24        }
25        return sum;
26    }
27};
28
29class Solution {
30public:
31    vector<int> minDeletions(string s, vector<vector<int>>& queries) {
32        int length = s.size();
33
34        // marks[i] == 1 means s[i] equals its previous character s[i-1].
35        // Each such adjacent equal pair requires exactly one deletion to fix.
36        vector<int> marks(length, 0);
37        BinaryIndexedTree bit(length);
38
39        // Initialize marks and the Fenwick tree based on adjacent equal pairs.
40        for (int i = 1; i < length; i++) {
41            marks[i] = (s[i] == s[i - 1]);
42            if (marks[i]) {
43                bit.update(i + 1, 1);  // Tree is 1-indexed, so store at i + 1
44            }
45        }
46
47        vector<int> answer;
48
49        for (auto& query : queries) {
50            if (query[0] == 1) {
51                // Type 1: toggle the character at position `pos`.
52                // Toggling affects the equality relation at `pos` (with pos-1)
53                // and at `pos + 1` (with pos), so update both marks.
54                int pos = query[1];
55
56                // Flip the mark at `pos` and reflect the change in the tree.
57                int delta = (marks[pos] ^ 1) - marks[pos];
58                marks[pos] ^= 1;
59                bit.update(pos + 1, delta);
60
61                // Flip the mark at `pos + 1` if it exists.
62                if (pos + 1 < length) {
63                    delta = (marks[pos + 1] ^ 1) - marks[pos + 1];
64                    marks[pos + 1] ^= 1;
65                    bit.update(pos + 2, delta);
66                }
67            } else {
68                // Type 2: count the deletions needed within range [left, right].
69                // This equals the number of marked positions in (left, right],
70                // which is the count of adjacent equal pairs in that substring.
71                int left = query[1];
72                int right = query[2];
73                answer.push_back(bit.query(right + 1) - bit.query(left + 1));
74            }
75        }
76        return answer;
77    }
78};
79

1// Size of the Binary Indexed Tree (Fenwick Tree)
2let treeSize: number;
3
4// 1-indexed array storing the Binary Indexed Tree
5let treeArray: number[];
6
7/**
8 * Adds `delta` to position `x` and propagates the change
9 * to all responsible nodes in the Fenwick Tree.
10 */
11function update(x: number, delta: number): void {
12    while (x <= treeSize) {
13        treeArray[x] += delta;
14        x += x & -x; // move to the next node that covers position x
15    }
16}
17
18/**
19 * Returns the prefix sum from index 1 up to index `x`.
20 */
21function query(x: number): number {
22    let sum = 0;
23    while (x > 0) {
24        sum += treeArray[x];
25        x -= x & -x; // move to the parent prefix node
26    }
27    return sum;
28}
29
30/**
31 * For each "count" query, returns the number of deletions required
32 * so that no two adjacent characters in s[l..r] are equal.
33 * A deletion is needed wherever s[i] === s[i - 1].
34 */
35function minDeletions(s: string, queries: number[][]): number[] {
36    const n = s.length;
37
38    // nums[i] = 1 means s[i] equals s[i - 1] (an adjacent duplicate pair)
39    const nums: number[] = Array(n).fill(0);
40
41    // Initialize the Fenwick Tree as a fresh global structure
42    treeSize = n;
43    treeArray = Array(n + 1).fill(0);
44
45    // Record every adjacent duplicate pair in the BIT
46    for (let i = 1; i < n; i++) {
47        if (s[i] === s[i - 1]) {
48            nums[i] = 1;
49            update(i + 1, 1);
50        }
51    }
52
53    const ans: number[] = [];
54
55    for (const q of queries) {
56        if (q[0] === 1) {
57            // Update query: flip the character at index j.
58            const j = q[1];
59
60            // Toggle the pair (j - 1, j) stored at nums[j]
61            let delta = (nums[j] ^ 1) - nums[j];
62            nums[j] ^= 1;
63            update(j + 1, delta);
64
65            // Toggle the pair (j, j + 1) stored at nums[j + 1], if it exists
66            if (j + 1 < n) {
67                delta = (nums[j + 1] ^ 1) - nums[j + 1];
68                nums[j + 1] ^= 1;
69                update(j + 2, delta);
70            }
71        } else {
72            // Count query: number of duplicate pairs within [l, r].
73            // Pairs are counted at their right index, so the valid range
74            // in BIT terms is (l + 1, r + 1].
75            const l = q[1];
76            const r = q[2];
77            ans.push(query(r + 1) - query(l + 1));
78        }
79    }
80
81    return ans;
82}
83