CF372B Counting Rectangles is Fun

There is an $ n×m $ rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the $ i $ -th row and the $ j $ -th column as $ (i,j) $ . Let's define a "rectangle" as four integers $ a,b,c,d $ $ (1

N/A

N/A

For the first example, there is a $ 5×5 $ rectangular grid, and the first, the second, and the third queries are represented in the following image. - For the first query, there are $ 10 $ good rectangles, five $ 1×1 $ , two $ 2×1 $ , two $ 1×2 $ , and one $ 1×3 $ . - For the second query, there is only one $ 1×1 $ good rectangle. - For the third query, there are $ 7 $ good rectangles, four $ 1×1 $ , two $ 2×1 $ , and one $ 3×1 $ .