20182019 ACMICPC, Asia Shenyang Regional Contest E题解
[E. The Kouga Ninja Scrolls][http://codeforces.com/gym/101955/problem/E]
The story centres around $n$ rival ninja clans labelled from $1$ to $n$, and nn ninjas also labelled from $1$ to $n$. For each ninja, the family decides his/her initial belief and affiliation of a clan. But some conflicts occur in the story, such as two young souls, facing the rivalry between their ninjas but falling in love, can change their mind and some ninjas may desert to other opposite clans.
These ninjas are living in a pretty quiet town with straightforward footpaths, but they live like a group of wild animals eyeing up ninjas of other clans, continually escaping and looking forward to killing. The governor of this region knows that the end of the war between them depends on those ninjas belonging to different clans who have the farthest distance.
That is what a noble vulture as the honest servant of the governor should do. Now you need to act as a vulture, and report in real time to the governor the largest distance between two ninjas that belong to different clans and whose labels are in a specified consecutive range. As a practical matter, the distance between two points in the plane is defined as the Manhattan distance, which is equal to the sum of the absolute differences of their Cartesian coordinates.
Input
The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $60$.
For each test case, the first line contains two integers $n$, indicating the number of clans and also the number of ninjas, and $m$, indicating the total number of special conflicts and inquiries from the governor, where $1≤n≤10^5$ and $1≤m≤10^5$.
The following $n$ lines describe the initial situations of all ninjas. The $i$th line of them contains three integers $x,y$ and $c$ indicating the initial position where the $i$th ninja stays is $(x,y)$ and the initial clan which he/she belongs to is the $c$th one, where $−10^9≤x,y≤10^9$and $1≤c≤n$.
Then the following $m$ lines describe all special conflicts that change someone’s position or his/her clan, and all inquiries from the governor in chronological order. Each of them must be in one of the following forms.
 1 k x y, the $k$th ninja changes his/her position along the direction $(x,y)$; that is to say, he/she moves to the new position $(x_0+x,y_0+y)$ where $(x_0,y_0)$ is his/her original position.
 2 k c, the $k$th ninja changes his/her mind and decides to work for the $c$th clan.
 3 l r, the governor asks his vulture for ninjas labelled from $l$ to $r$ (inclusive) the largest distance between two of them belonging to different clans.
All $k,x,y,l,r$ and $c$ mentioned in these $m$ lines satisfy $1≤k,c≤n$, $−10^9≤x,y≤10^9$ and $1≤l≤r≤n$.
We guarantee that the sum of $n$ in all test cases is no larger than $5×10^5$, and the sum of mm in all test cases is no larger than $5×10^5$ as well.
Output
For each test case, output a line containing “Case #x:” (without quotes) at first, where x is the test case number starting from $1$.
Then for each inquire, output an integer in a line indicating the answer. If all of the related ninjas belong to the same clan, output $0$ instead.
Example
input
1  12 80 0 11 1 23 1 21 1 1 13 1 21 1 1 12 1 23 1 22 1 13 1 2 
output
1  Case #1:2002 
Note
‘The Kouga Ninja Scrolls’ is a historical fantasy novel about ninja written in $19581959$ by the Japanese author Futaro Yamada. This is the first volume of the Ninja Scrolls series written by Yamada in $19582001$. The book has been translated into English by Geoff Sant and was published by Del Rey in December $2006$.
– from Wikipedia, the free encyclopedia
曼哈顿距离转切比雪夫距离 $max(x_1x_2,y_1y_2)$
原图 $(x,y)$ > 新图 $(x+y,xy)$，曼哈顿距离>切比雪夫距离
原图 $(x,y)$ > 新图 $(\frac{x+y}{2},\frac{xy}{2})$，切比雪夫距离>曼哈顿距离
之后x，y坐标就可以分开来维护了，只要各自求出最大值，最小值，相减得到x，y各自的最大差值，再比一下，得到答案。
但是有一点注意，x的最大值和最小值可能属于同一派，y也类似。
所以需要再维护次大和次小值，并且要求次大和最大的派别不同，次小和最小的派别不同。这可以保证维护这四个值一定可以得到派别不同的最大差值。
线段树维护，和不同线段树不同点在于pushup更新次大，次小时要比较和最大，最小的派别不同。
查询也类似。
1 
