p177.ans1
======================
63

=================
p177.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int B = 1024;

int n, m;
int sq;
vector<bitset<B>> grid;
vector<bitset<B>> set_1_lazy, set_0_lazy;
bitset<B> full_m;

void apply_lazy(int bucket) {
    int start = bucket * sq;
    int end = min(n, (bucket + 1) * sq);
    for(int i = start; i < end; i++) {
        grid[i] |= set_1_lazy[bucket];
        grid[i] &= ~set_0_lazy[bucket];
    }

    set_1_lazy[bucket] = bitset<B>(0);
    set_0_lazy[bucket] = bitset<B>(0);
}

void read() { cin >> n >> m; }

void solve() {
    // Sqrt decomposition over rows, each row stored as a bitset of columns.
    // Rows are grouped into buckets of size sq = sqrt(n); each bucket carries
    // two lazy column masks set_1_lazy / set_0_lazy describing pending "set to
    // white" / "set to black" operations that apply uniformly to every row in
    // the bucket. A repaint of rows [x1, x2], columns [y1, y2] touches the two
    // boundary buckets directly (apply_lazy flushes them first, then we edit
    // the affected rows by OR-ing / AND-ing the column mask) and updates only
    // the lazy masks of fully covered interior buckets in O(1). Setting one
    // colour clears the conflicting lazy bits for the same columns. At the end
    // all buckets are flushed and we count the white (set) bits.

    sq = sqrt(n) + 1;
    grid.assign(n, bitset<B>());
    set_1_lazy.assign(sq, bitset<B>());
    set_0_lazy.assign(sq, bitset<B>());

    full_m = bitset<B>();
    for(int i = 0; i < n; i++) {
        full_m.set(i);
    }

    for(int i = 0; i < n; i++) {
        grid[i] = full_m;
    }

    while(m--) {
        int x1, y1, x2, y2;
        string c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        x1--;
        y1--;
        x2--;
        y2--;

        if(x1 > x2) {
            swap(x1, x2);
        }

        if(y1 > y2) {
            swap(y1, y2);
        }

        bool color = (c == "w");
        bitset<B> mask = (full_m >> (n - (y2 - y1 + 1))) << y1;

        int r1 = x1 / sq, r2 = x2 / sq;

        if(r1 == r2) {
            apply_lazy(r1);
            for(int i = x1; i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }
        } else {
            apply_lazy(r1);
            for(int i = x1; i < (r1 + 1) * sq && i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }

            apply_lazy(r2);
            for(int i = r2 * sq; i <= x2; i++) {
                if(color) {
                    grid[i] |= mask;
                } else {
                    grid[i] &= ~mask;
                }
            }

            for(int i = r1 + 1; i < r2; i++) {
                if(color) {
                    set_1_lazy[i] |= mask;
                    set_0_lazy[i] &= ~mask;
                } else {
                    set_0_lazy[i] |= mask;
                    set_1_lazy[i] &= ~mask;
                }
            }
        }
    }

    int ans = 0;
    for(int bucket = 0; bucket * sq < n; bucket++) {
        apply_lazy(bucket);
    }

    for(int i = 0; i < n; i++) {
        ans += grid[i].count();
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p177.in1
======================
9 6
2 2 4 6 b
4 3 3 3 w
6 2 8 6 b
5 3 6 9 w
8 3 9 9 w
1 5 3 5 w

=================
statement.txt
======================
177. Square
time limit per test: 1.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



You have given the square NxN on a checkered sheet. Size of each cell is 1x1, (1, 1) is leftmost top corner and (N, N) is rightmost bottom corner.
Initially all cells are white.
There are M repaintings inside of the square, where one repainting changes color of specified rectangle to some color (white or black). All sides of repainted rectangles are parallel to sides of square.
You need to find amount of white cells after all repaintings.

Input
The first line of input consists of two numbers N and M (1<=N<=1000, 1<=M<=5000). Each of the next M lines consists of X1 Y1 X2 Y2 C, where (X1, Y1) and (X2, Y2) are indexes of opposite corners of the rectangular, and C is a symbol 'b' or 'w' ('b' means black color and 'w' - white) (1<=X1,X2,Y1,Y2<=N). All numbers in input are integer.

Output
Write amount of white cells after all repaintings.

Sample test(s)

Input
9 6
2 2 4 6 b
4 3 3 3 w
6 2 8 6 b
5 3 6 9 w
8 3 9 9 w
1 5 3 5 w

Output
63
Author:	Stanislav Angelyuk
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003

=================
