题目大意

给定一个 $n \times m$ 的数表，其中 $a_{i,j} = (i-1) \times m + j$。
需要在某列之间竖切或在某行之间横切，将表格分成两部分，使得两部分和的最大值最小。
输出切割方案（优先竖切，其次取最小列/行号）。

解题思路

数表性质

• 数表是从 $1$ 到 $n \times m$ 的连续整数按行排列
• 总和：$S = \frac{n \times m \times (n \times m + 1)}{2}$

切割方式

1. 竖切在第 $i$ 列：

   • 左边部分包含前 $i$ 列
   • 每行左边部分是一个等差数列：$[(r-1)m+1, (r-1)m+i]$
   • 左边总和：$T_v = \sum_{r=1}^n \sum_{c=1}^i [(r-1)m + c] = \frac{n \cdot i \cdot (i + 1 + nm - m)}{2}$

2. 横切在第 $i$ 行：

   • 上边部分包含前 $i$ 行
   • 每行是一个完整的 $1$ 到 $m$ 的等差数列偏移
   • 上边总和：$T_h = \sum_{r=1}^i \sum_{c=1}^m [(r-1)m + c] = \frac{m^2 \cdot i^2 + m \cdot i}{2}$

最优位置分析

目标是使 $\max(T, S-T)$ 最小，即让 $T$ 尽可能接近 $S/2$。

代码通过数学推导找到近似最优的切割位置：

• 对于竖切：解方程 $T_v \approx S/2$ 得到近似位置 $sp$
• 对于横切：解方程 $T_h \approx S/2$ 得到近似位置 $sp$
• 在 $[sp, sp+1]$ 范围内枚举验证找到实际最优解

复杂度分析

• 时间复杂度：$O(t)$，每组数据只进行常数次计算和比较
• 空间复杂度：$O(1)$，只使用几个变量

关键点

1. 数学推导：通过解二次方程找到近似最优切割位置
2. 局部枚举：在理论值附近小范围枚举确保找到最优解
3. 优先级处理：按题目要求优先竖切，其次取最小索引
4. 大数处理：使用 long long 防止溢出