题意
在一个王国里，有N个人。第i个人住在一个点上（xi, yi）。你是一个怪物，需要绕过王国，抓住所有N个人。
你从某个点开始（u，v）。
在1秒内，你可以从点（u，v）移动到点（u'，v'），其中|u'-u|≤1，|v'-v|≤1。这意味着在1秒内你可以移动到8个相邻的点。你也可以停留在同一位置（这毫无意义）。
你的旅程将是这样的：
你从（u，v）开始
你走到(x1, y1)的第一个人面前，立即抓住他。
然后你需要回到你的家，并休息2秒。
然后你去找位于（x2，y2）的第二个人，立即抓住他。
然后你需要回到你的家，休息2秒。
这样重复下去，直到你抓到所有N个人。
你必须处理2种类型的Q查询：
0 - 第i个人移动到某个新点（xi', yi'）。
1 - 如果你从点（u，v）开始，完成旅程的最短时间是多少？
在这个问题中，你将得到整数BASE和多个查询。你将不得不设置初始值T=0。
0类型的查询意味着指定的人移动到点（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）。
对于类型1的查询，你需要输出捕获所有的人的旅程的最小时间，如果你将从坐标（（a1 * T + b1）%BASE，（a2 * T + b2）%BASE）开始。你应该用计算出的时间更新T的值。
在第一行输入中，有三个整数N、Q和BASE（0≤N、Q≤105，0≤BASE≤109。在接下来的N行中，有两个整数xi和yi（0≤xi, yi≤BASE）--人们的坐标。
在下面的Q行中，有以下类型的查询：
0 i a1 b1 a2 b2
1 a1 b1 a2 b2
其中i是人的索引（1≤i≤N），a1、b1、a2、b2是前面提到的值（0≤a1、b1、a2、b2≤109）。
解题思路
考虑抓每一个人都是独立的，只需要找到去每一个点的最短距离\(\times2\)(要回来)，再加上2N-2秒的休息就行了。
Part 1 如何使抓人移动次数最短
根据题意，每一次移动可使横纵坐标之差分别减去0或1，所以移动次数最短就是横纵坐标差的最大值。
如下图，假设怪物在(-1,-1),人在(3,2),那么横坐标差了4，纵坐标差3，最少移动次数为4。
Part 2 如何计算
看上去速度很快，实则1e10。
设怪物所在位置为(x1,y1)，要抓的人在(x2,y2)，移动次数为S，根据Part1有：
$ S=max\left ( |x1-x2|,|y1-y2| \right )\( \)=max\left ( x1-x2,x2-x1,y1-y2,y2-y1 \right ) $
其实就是切比雪夫距离，我们知道切比雪夫距离和曼哈顿距离是可以互化的。
对点(x,y),把它转化为点(x+y,x-y),此时怪物在(x1-y1,x1+y1),人在点(x2-y2,x2+y2)
此时计算曼哈顿距离为
$max\left ( x1+y1-x2-x2,x2+y2-x1-y1,x1-y1-x2+y2,x2-y2-x1+y1 \right ) $
化简一下：
$max\left ( 2x1-2x2,2y2-2y1,2y1-2y2,2x2-2x1 \right ) \(，是所求的两倍！！（返程不用\)\times2$了）
剩下的交给动态二维偏序
标签：Life,y2,Monster,y1,BASE,b1,x2,x1 From： https://www.cnblogs.com/wangwenhan/p/17584902.html