Number of Times Binary String Is Prefix-Aligned LeetCode solution in C++

1
class BIT {
2
 public:
3
  vector<int> bit;
4
  int n;
5
  BIT(int n) {
6
    bit.resize(n + 1, 0);
7
    this->n = n;
8
  }
9

10
  int findSum(int i) {
11
    int sum = 0;
12
    while (i > 0) {
13
      sum += bit[i];
14
      i -= (i & (-i));
15
    }
16
    return sum;
17
  }
18

19
  void update(int i, int val) {
20
    while (i <= n) {
21
      bit[i] += val;
22
      i += (i & (-i));
23
    }
24
  }
25
};
26

27
class Solution {
28
 public:
29
  int numTimesAllBlue(vector<int> &flips) {
30
    int n = flips.size();
31
    BIT tree(n + 1);
32
    int res = 0;
33
    string s = string(n, '0');
34

35
    int maxi = 0;
36
    for (auto &x : flips) {
37
      if (s[x - 1] == '1') {
38
        tree.update(x, -1);
39
        s[x - 1] = '0';
40
      } else {
41
        s[x - 1] = '1';
42
        tree.update(x, 1);
43
      }
44
      maxi = max(maxi, x);
45
      if (tree.findSum(x) == x && tree.findSum(maxi) == maxi) res++;
46
    }
47

48
    return res;
49
  }
50
};