对于每一次切割后，求出最大的碎片面积，也就是求出完整的玻璃的最大长度与最大宽度之积。
由题意可知，一条长度为 $k$ 的边，最多可以被切 $k - 1$ 次，因为在此之后均为长度为 $1$ 的边无法在切割。于是我们就可以用 $0$ 或 $1$ 来表示该边的某个点是否被切割，总共表示 $k - 1$ 个点。初始的时候每个点均为 $0$，表示所有的点均未被切割，每输入一次后将相应的切割点标记为 $1$。于是乎，不难将问题转化成求每次切割后每条边的最长 $0$ 的个数。
考虑用线段树来维护，一棵线段树共有以下参数：len、l、r 与 mx，分别表示区间的长度、从左端点最长 $0$ 的个数、从右端点最长 $0$ 的个数以及该区间最长 $0$ 的个数。
下面我将分别讲述 build 、 modify 与 pushup 函数。
在 build 函数中，因初始时均为 $0$，所以每段区间的 l、r 与 mx 的值均为 len，即 $r - l + 1$，有以下代码：
1
2
3
4
5
6
7
8
9
| void build (T tree[],int cur,int l,int r)
{
tree[cur].l = tree[cur].r = tree[cur].mx = tree[cur].len = r - l + 1;
if (l == r) return ;
int mid = (l + r) >> 1;
build (tree,cur << 1,l,mid);
build (tree,cur << 1 | 1,mid + 1,r);
pushup (tree,cur);
}
|
在 modify 函数中，由题可知是一个单点的修改，因此我们只需要在 $l = r$ 之时把该点的值改为 $1$，表示已被切割就可以了。同时，该区间的 l、r 与 mx 因数值的变化均会变为 $0$。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| void modify (T tree[],int cur,int l,int r,int x)
{
if (l == r && x == l)
{
tree[cur].l = tree[cur].r = tree[cur].mx = 0;
return ;
}
int mid = (l + r) >> 1;
if (x <= mid) modify (tree,cur << 1,l,mid,x);
else modify (tree,cur << 1 | 1,mid + 1,r,x);
pushup (tree,cur);
}
|
最后来讲 pushup 函数，每个区间在更新后除长度不会改变外其余均有变动。首先是 l 的值，分两种情况，若从左端点最长 $0$ 的个数与区间长度相等，则说明正一段区间均为 $0$，因此可以更新至右区间的左端 $0$ 所能达到的最远之处，相加即可；否则就是左端点的 l 的值。r 的值同理分两种情况，不再赘述。同时，需要更新区间 mx，易得有三种情况，分别为左端点开始最长的 $0$ 的个数，右端点开始最长的 $0$ 的个数以及序列中间最长的 $0$ 的个数，三者取最值就能更新答案了。代码如下：
1
2
3
4
5
6
7
8
| void pushup (T tree[],int cur)
{
if (tree[cur << 1].l == tree[cur << 1].len) tree[cur].l = tree[cur << 1].len + tree[cur << 1 | 1].l;
else tree[cur].l = tree[cur << 1].l;
if (tree[cur << 1 | 1].r == tree[cur << 1 | 1].len) tree[cur].r = tree[cur << 1 | 1].len + tree[cur << 1].r;
else tree[cur].r = tree[cur << 1 | 1].r;
tree[cur].mx = max (tree[cur << 1].mx,max (tree[cur << 1 | 1].mx,tree[cur << 1].r + tree[cur << 1 | 1].l));
}
|
最后给出主函数，查询即为下标为 $1$ 的线段树的数组的 mx 值，但返回的答案记得 $+1$，画一下图就能悟了哦！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int main ()
{
m = read ();n = read ();q = read ();
build (tree_l,1,1,n - 1);build (tree_h,1,1,m - 1);
while (q--)
{
char x;int num;
scanf ("%c",&x);num = read ();
if (x == 'H') modify (tree_l,1,1,n - 1,n - num);
else modify (tree_h,1,1,m - 1,num);
ll da = tree_h[1].mx + 1,db = tree_l[1].mx + 1;
printf ("%lld\n",da * db);
}
return 0;
}
|
