DouKaku?

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cassert>

#define REP(i, b, e) for (size_t i = b; i < e; ++i)

struct rect
{
    long left, bottom, right, top;
};

template <typename T>
void sort_and_unique(std::vector<T>& v)
{
    std::sort(v.begin(), v.end());

    v.erase(std::unique(v.begin(), v.end()), v.end());
}

template <typename T>
size_t find(const std::vector<T>& v, const T& value)
{
    std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);

    assert(it != v.end());

    return it - v.begin();
}

int main()
{
    long w, h;

    std::cin >> w >> h;

    assert(0 <= w && w <= 1000000);
    assert(0 <= h && h <= 1000000);

    size_t n;

    std::cin >> n;

    assert(1 <= n && n <= 1000);

    std::vector<rect> tapes;

    for (; n; --n)
    {
        rect r;

        std::cin >> r.left >> r.bottom >> r.right >> r.top;

        assert(0 <= r.left && r.left < r.right && r.right <= w);

        assert(0 <= r.bottom && r.bottom < r.top && r.top <= h);

        tapes.push_back(r);
    }

    std::vector<long> xs(2); xs[0] = 0; xs[1] = w;
    std::vector<long> ys(2); ys[0] = 0; ys[1] = h;

    for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
    {
        xs.push_back(it->left);
        xs.push_back(it->right);
        ys.push_back(it->bottom);
        ys.push_back(it->top);
    }

    sort_and_unique(xs);
    sort_and_unique(ys);

    const size_t xn = xs.size() - 1;
    const size_t yn = ys.size() - 1;

    std::vector<std::vector<int> > map(xn, std::vector<int>(yn, true));

    for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
    {
        const size_t lower_xi = find(xs, it->left);
        const size_t upper_xi = find(xs, it->right);
        const size_t lower_yi = find(ys, it->bottom);
        const size_t upper_yi = find(ys, it->top);

        REP(xi, lower_xi, upper_xi) REP(yi, lower_yi, upper_yi)
        {
            map[xi][yi] = false;
        }
    }

    size_t count = 0;

    REP(xi, 0, xn) REP(yi, 0, yn) if (map[xi][yi])
    {
        ++count;

        std::queue<std::pair<size_t, size_t> > q;

#define PUSH(XI, YI) if (map[XI][YI]) { map[XI][YI] = false; q.push(std::make_pair(XI, YI)); }

        PUSH(xi, yi);

        while (! q.empty())
        {
            const size_t xj = q.front().first;

            const size_t yj = q.front().second;

            q.pop();

            if (xj >= 1) // left
            {
                PUSH(xj - 1, yj);
            }

            if (yj >= 1) // top
            {
                PUSH(xj, yj - 1);
            }

            if (xj + 1 < xn) // right
            {
                PUSH(xj + 1, yj);
            }

            if (yj + 1 < yn) // bottom
            {
                PUSH(xj, yj + 1);
            }
        }

#undef PUSH

    }

    std::cout << count << std::endl;
}