树状数组

一上来发现这道题目涉及区间查询与单点修改。

单点修改：每次翻转二进制串中的一个位置，可以视为单点加一减一。
区间查询：查询串中\([1, i]\)中是否全为1，等价于查询\([1, i]\)的区间和是否为i。

结合数据范围\(n \leq 5 \times 10^4\)，\(O(nlogn)\)的树状数组解法可以过。

class Solution {
public:
    int n;
    vector<int> s;
    vector<int> tr; // 树状数组

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int x, int y)
    {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += y;
    }

    int query(int x)
    {
        int res = 0;
        for (int i = x; i; i -= lowbit(i))
            res += tr[i];
        return res;
    }

    int numTimesAllBlue(vector<int>& flips) 
    {
        n = flips.size();
        s = vector<int>(n + 1, 0);
        tr = vector<int>(n + 1);

        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            int t = i + 1;
            int idx = flips[i]; // 反转下标idx处的数字
            if (s[idx] == 0)
            {
                s[idx] = 1;
                add(idx, 1);
                if (query(t) == t) ++res;
            }
            else
            {
                s[idx] = 0;
                add(idx, -1);
                if (query(t) == t) ++res;
            }
        }
        return res;
    }
};

枚举

这道题目的flips数组是对\([1,n]\)中所有数字的一个排列。所以最终所有的数字肯定都会被翻转的。
那么第i次翻转会不会导致前i个位全为1，就等价于问前i次翻转的最大下标是否为i。如果发现了这个性质，那么实际上一遍循环就可以解决了。复杂度\(O(n)\)。

impl Solution {
    pub fn num_times_all_blue(flips: Vec<i32>) -> i32 {
        let (mut res, mut max_idx) = (0, 0);
        for (i, flip) in flips.into_iter().enumerate() {
            max_idx = std::cmp::max(max_idx, flip);
            if max_idx == i as i32 + 1 { res += 1; }
        }
        res
    }
}