P10299 [CCC 2024 S5] Chocolate Bar Partition

Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。 如果可以通过向上、向下、向左或向右移动的方式访问到每个小方块，则该部分被视为一个连通块。

输入的第一行包含一个正整数 $N$ 表示巧克力的长度。 第二行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第一行第 $j$ 个小方块的美味度 $T_{1,j}$。 类似地，第三行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第二行第 $j$ 个小方块的美味度 $T_{2,j}$。

输出一个整数，表示 Maxwell 最多能把巧克力切分出的连通块数。

**【样例 1 解释】** 把巧克力分割成 $2$ 块是最优的，一种方案是把右下角的一个小方块作为一个连通块，其余三个小方块作为第二个连通块，如下图所示。  每一个连通块的平均美味度都为 $5$。 **【样例 2 解释】** 一种获得平均分割巧克力的方案如下图所示：  注意每一块的平均美味度都为 $1$。 **【数据范围】** **本题采用捆绑测试。** 对于所有数据，保证 $1 \leq N \leq 2 \times 10^5$，$0 \leq T_{i,j} \leq 10^8$。 下面的表格显示了 $15$ 分的分配方案： | 分值 | $N$ 的范围 | $T_{i,j}$ 的范围 | | :-: | :-: | :-: | | $2$ | $N = 2$ | $0 \leq T_{i,j} \leq 5$ | | $2$ | $1 \leq N \leq 8$ | $0 \leq T_{i,j} \leq 20$ | | $1$ | $1 \leq N \leq 20$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 100$ | $0 \leq T_{i,j} \leq 20$ | | $2$ | $1 \leq N \leq 1000$ | $0 \leq T_{i,j} \leq 100$ | | $3$ | $1 \leq N \leq 2000$ | $0 \leq T_{i,j} \leq 10^5$ | | $3$ | $1 \leq N \leq 2 \times 10^5$ | $0 \leq T_{i,j} \leq 10^8$ |