33OJ
登录 注册

#P17500. [ICPC 2026 Wuhan I] Rectangle Cutting

[ICPC 2026 Wuhan I] Rectangle Cutting

题目描述

八千代在平面直角坐标系的第一象限内有一个矩形。该矩形的左下角位于坐标原点 (0,0)(0,0),右上角位于 (n,m)(n,m)。换言之,矩形的两边分别与 xx 轴、yy 轴重合,其在 xx 轴方向的长度为 nn,在 yy 轴方向的长度为 mm。

八千代决定把这个矩形切 qq 刀。具体地,她有以下两种切割方式:

  • 横向切割:给定一个正整数 kk,沿着直线 y=ky=k 进行切割。
  • 纵向切割:给定一个正整数 kk,沿着直线 x=kx=k 进行切割。

每次切割都会贯穿整个区域,将现有的矩形进一步切割成更多的小矩形。

八千代想要知道,在每一次切割完成之后,当前所有被切分出来的小矩形中,面积的最大值是多少?

输入格式

第一行包含三个整数 n,m,qn,m,q(1≤n,m≤1091 \le n,m \le 10^9,1≤q≤5×1051 \le q \le 5\times10^5),分别表示初始矩形的水平长度、垂直长度以及切割的次数。

接下来 qq 行,每行包含两个整数 op,kop,k,描述一次切割操作:

  • 若 op=1op=1,表示进行一次纵向切割,给定整数 kk(1≤k<n1 \le k<n),沿着直线 x=kx=k 切割。
  • 若 op=2op=2,表示进行一次横向切割,给定整数 kk(1≤k<m1 \le k<m),沿着直线 y=ky=k 切割。

保证八千代绝对不会在同一个位置切割两次(即所有的切割直线均互不相同)。

输出格式

输出共 qq 行,每行包含一个整数,第 ii 行的整数表示在第 ii 次切割之后,所有小矩形中面积的最大值。

5 3 3
1 1
1 4
2 2
12
9
6

提示

:::align{center}

图 1:样例解释 :::