CF527C Glass Carving

题目描述

Leonid 想成为一名玻璃雕刻师(即通过切割玻璃创作出精美艺术品的人)。他已经有一块 $w$ 毫米 $\times$ $h$ 毫米的矩形玻璃、一把金刚石玻璃刀以及满腔热情。现在唯一缺少的就是知道该如何雕刻以及雕刻什么。 为了不浪费时间练习技艺,他决定仅仅锻炼切割技术。具体方法为:他每次都在整块玻璃上进行一次垂直或水平切割。这样一来,玻璃就会分裂成许多更小的矩形碎片。Leonid 不会移动新切割出来的玻璃碎片。特别地,每次切割都会把它经过的每一个玻璃碎片分成两个更小的碎片。 每完成一刀,Leonid 就会想知道目当前所拥有的最大玻璃碎片的面积是多少。由于碎片会越来越多,思考这个问题也会花费他越来越多的时间,分散了雕刻的乐趣。 Leonid 希望你和他分工——他负责切玻璃,你负责在每次切割后计算当前最大碎片面积。你同意么?

输入格式

第一行包含三个整数 $w, h, n$($2 \leq w, h \leq 200000$,$1 \leq n \leq 200000$)。 接下来的 $n$ 行,每行描述一次切割,形如 $H\ y$ 或 $V\ x$。其中 $H\ y$ 表示在距离原始玻璃下边缘 $y$ 毫米处进行一次水平切割($1 \leq y \leq h-1$),$V\ x$ 表示在距离原始玻璃左边缘 $x$ 毫米处进行一次垂直切割($1 \leq x \leq w-1$)。保证不会有两次相同的切割。

输出格式

每完成一次切割,在单独一行输出当前所有玻璃碎片中面积最大的碎片面积(单位:$\mathrm{mm}^2$)。

说明/提示

第一组样例的示意图如下: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF527C/6468d2fd0321178fa316ccb774411f002769e9ee.png) 第二组样例的示意图如下: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF527C/40ba2772b27431a21bc874ab308dc348ec8365fd.png) 由 ChatGPT 5 翻译