矩形切割

有一个w*h的矩形，每次对它横着切一刀，或者竖着切一刀，每一刀切完之后，有若干个矩形会被分成两个更小的矩形。每一刀切完之后，请找出所有矩形中面积最大的。

输入

第一行是三个整数w h n表示矩形的宽度和高度,以及操作的数量

接下来n行每行一个操作

是下列两种形式之一：

H y (表示横着在离矩形下边界y的位置切一刀)

V x(表示竖着在离矩形左边界x的位置切一刀)

$\le w, h \le 200000, 1 \le n \le 2000002≤ w,h≤ 200000,1≤ n≤ 200000$

1 ≤ y ≤ h - 1,1 ≤ x ≤ w - 1

输出

每次操作之后输出一行，表示当前最大矩形的面积。

样例

输入

复制

输出

复制

输入

复制

输出

复制

提示

子任务1，20分， $\le n \le 1001≤ n≤ 100$

子任务2，80分，全范围

横着切和竖着切互不影响，我们每次只需要找出最大的宽和最大的高相乘就可以了，可以用优先队列，但是对于被切割的块又不能准确定位，可以用set记录切刀的位置，当队列头部被切割过时再进行更新。

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <set>
#include <algorithm>
#include <functional>
#define inf 0x3f3f3f3f
int main()
{
    int w, h, n;
    char op[2];
    int d;
    std::priority_queue < std::pair<int, int>, std::vector<std::pair<int, int>>, std::less<std::pair<int, int>>> qr, qc;
    scanf("%d%d%d", &w, &h, &n);
    qr.push(std::make_pair(h, 0));
    qc.push(std::make_pair(w, 0));
    std::set<int> cutR, cutC;
    cutR.insert(0);
    cutR.insert(h);
    cutC.insert(0);
    cutC.insert(w);
    for (int i = 0; i < n; i++)
    {
        scanf("%s%d", op, &d);
        if (op[0] == 'V')
        {
            cutC.insert(d);
        }
        else
        {
            cutR.insert(d);
        }
        bool flag = true;
        while (flag)
        {
            int l = qr.top().second;
            int r = l + qr.top().first;
            std::set<int>::iterator it = cutR.lower_bound(l);
            while (*it != r)
            {
                if (*it != l)
                {
                    qr.push(std::make_pair(*it - l, l));
                    l = *it;
                }
                it++;
            }
            if (l != qr.top().second)
            {
                qr.push(std::make_pair(*it - l, l));
                qr.pop();
            }
            else
            {
                flag = false;
            }
        }
        flag = true;
        while (flag)
        {
            int l = qc.top().second;
            int r = l + qc.top().first;
            std::set<int>::iterator it = cutC.lower_bound(l);
            while (*it != r)
            {
                if (*it != l)
                {
                    qc.push(std::make_pair(*it - l, l));
                    l = *it;
                }
                it++;
            }
            if (l != qc.top().second)
            {
                qc.push(std::make_pair(*it - l, l));
                qc.pop();
            }
            else
            {
                flag = false;
            }
        }
        printf("%lld\n", (long long)qr.top().first * qc.top().first);
    }
    return 0;
}

如果觉得有帮助，点个推荐啦~