国庆牛客集训的题,正好准备好好训练线段树,想起来就补一下。

题意很简单,两种操作行合并或者列合并,每个操作后计算有多少个子块。

这题应该先推导公式,行操作或者列操作只有一种的时候,很简单,总数就是n*m - 有多少行或列合并了*一列多少格子m或者一行多少格子n + 合并的行或者列数。

两种都在,就需要结合图示来理解一下,简单的容斥一下,总数就是n*m - 行列各自算一遍上述的, 再加上行列重叠的,再加上最终行列合成的一块。

然后根据公式,

我们发现这里需要维护的是1~n和m的行或者列,有多少行或者列已经被合并了,n和m最大到1e9,而且不能离散化,(离散化我也不会,

05-11 22:19