Since the number of available and unavailable squares are both enormous, it is difficult to directly manage them.
Here, consider the squares covered by the pieces in multiple different directions. The number of such squares is estimated as \(O(M ^ 2)\).

Thus, the problem can be solved by, when inspecting the squares affecting in a certain direction, counting the squares that have been inspected so far. (After reducing the pieces in the same line, the total number of squares that are found to be already counted adds up to\(O(M ^ 2)\).)

The time complexity is estimated as \(O(M ^ 2)\) or \(O(M ^ 2\log M)\).

The sample code is as follows.

#include <iostream>
#include <set>

int main(){
    using namespace std;
    unsigned N, Q;
    cin >> N >> Q;

    // horizontal, vertical, and (anti)diagonal effects
    set<unsigned> horizontal, vertical, diagonal_slash, diagonal_backslash;
    for (unsigned i{}; i < Q; ++i){
        unsigned x, y;
        cin >> x >> y;
        horizontal.emplace(x);
        vertical.emplace(y);
        diagonal_slash.emplace(x + y);
        diagonal_backslash.emplace(x - y);
    }

    // vertical and horizontal effects can be immediately counted
    unsigned long ans{(N - size(horizontal)) * (N - size(vertical))};

    // anti-diagonal（with constant x + y）
    for (const auto d : diagonal_slash) {
        // the x coordinates of already inspected squares
        set<unsigned> cross_x;
        for (const auto x : horizontal)
            // insert if the intersection is inside
            if (1 <= d - x && d - x <= N)
                cross_x.emplace(x);
        for (const auto y : vertical)
            // insert if the intersection is inside
            if (1 <= d - y && d - y <= N)
                cross_x.emplace(d - y);

        // # squres (2 min(d, N + 1) - d - 1) subtracted by # already inspected squares is # newly found squares (# means "the number of")
        ans -= 2 * min(d, N + 1) - d - 1 - size(cross_x);
    }

    // diagonal（with constant x - y）
    for (const auto d : diagonal_backslash) {
        // the x coordinates of already inspected squares
        set<unsigned> cross_x;
        for (const auto x : horizontal)
            // insert if the intersection is inside
            if (1 <= x - d && x - d <= N)
                cross_x.emplace(x);
        for (const auto y : vertical)
            // insert if the intersection is inside
            if (1 <= d + y && d + y <= N)
                cross_x.emplace(d + y);
        for (const auto e : diagonal_slash)
            // insert if the intersection is inside
            if ((d + e) % 2 == 0 && 1 <= (d + e) / 2 && (d + e) / 2 <= N && 1 <= (e - d) / 2 && (e - d) / 2 <= N)
                cross_x.emplace((d + e) / 2);
        
        // # squares N - |d| subtracted by # already inspected squares is # newly found squares
        ans -= N - min(d, -d) - size(cross_x);
    }

    cout << ans << endl;
    return 0;
}