[T535983]Pandasun的糖果

以下为题目

PandaSun的糖果

题目背景

idea by wizard

PandaSun超级喜欢糖果，也非常喜欢排列，他有一个糖果阵，在每次取糖果吃的时候，他需要维护糖果阵的整齐。

请你帮PandaSun维护一下，PandaSun会给你糖吃。

题目描述

PandaSun有一个 $n$ 行 $m$ 列的糖果阵，每一次吃糖果，他都会选择 $r$ 行 $c$ 列的糖果吃掉。

从 $1$ 开始，按照行大号顺序给每个人编号，即编号为 $(r−1)⋅m+c
$ 的人最初位于 $(r,c)$。

为了维护每一次糖果阵的整齐，PandaSun会使用递补策略。

比如说PandaSun要吃这个红色糖果，他最后的糖果阵就会变成图三那样。

爱科学的PandaSun想算出他每次吃糖果的贡献值。

贡献值的算法：

贡献值是每个移动的糖移动的曼哈顿距离之和。

如果某一个糖最初在 $(r_0,c_0)$，然后移动到 $(r_1,c_1)$，则曼哈顿距离为 $|r_0−r_1|+|c_0−c_1|$。

输入格式

第一行包含一个整数 $t
( 1≤t≤10^4
)$ - 测试用例数。

每个测试用例的唯一一行包含 4
个整数 $n$
、 $m$
、 $r$
和 $c(1≤r≤n≤10^6
, 1≤c≤m≤10^6
)$，其中 $n$
是行数， $m$
是列数， $(r,c)$
是离开糖最初所在的位置。

输出格式

对于每组数据，直接输出贡献值即可。

样例 #1

样例输入 #1

1
2
3
4
5

4
2 3 1 2
2 2 2 1
1 1 1 1
1000000 1000000 1 1

样例输出 #1

1
2
3
4

6
1
0
1999998000000

提示

校正：PandaSun

第一次思考

主打一个跟着题目走，先写哈夫曼距离，然后是从编号到坐标，再从坐标到编号。极其的痛苦，而且还很失败，测试数据都过不了。

但是我一直在写这个，写了一周左右，直接删了，从头来！

第二次思考

优化哈夫曼距离计算

首先，我优化了哈夫曼距离这一段。因为这里糖果移动只存在2种可能：①在一行开头；②不在一行的开头。

对于①，其距离为m，为什么？因为挪动到上一行，其Δx为(m - 1),Δy为1(移动1行)。

对于②，就是1(没有动行，只前进一列)。

优化转换

这个题本身具有一定的迷惑性，它把一维编号与二维坐标混一块了，这就给我了一个错误的信号：必须互相转化。

但是，有了上一步的优化，我们可以不要二维坐标，因为不再需要计算哈夫曼距离，只需要判断当前糖果是否是每一列第一个，换句话说就是编号减1能被m整除，是的话就加m，不是就加1.这里我们甚至用三目运算符都OK！

完了？是，但是这样也会超时

第三次思考

于是我就在想有没有万能公式啊，还真有！

首先，我们先来计算从当前列到前一行了当前列的所有糖果向前移动的“贡献值”

第一步

我们观察可以发现，上述中一行糖果贡献值之和中只有一个是m，剩下的都是1.剩下了多少？m-1个，综上，我们可以知道，每跨一行，贡献值加 2m - 1。

第二步

既然每一行都一样没那不如一步到位，总共动(n - r)行，这应该很容易推到得到，于是我们得到了(n - r)(2m - 1)是从起始位置移动到最后一行同一列所有“贡献值”

第三步

OK呀胜利在望，只剩最后一行剩下的不分离，更简单(m - c)秒了 ，最终得到了(n - r)(2m - 1)+(m - c)这个公式，收工！

以上思路写下来的代码就可以过了，自己动手吧！

真的是纯cout好吗