最近做了一些曼哈顿距离的题。。整理一下吧。。
首先来看bzoj1604

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：
1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即|Xi – xi|+|Yi – Yi|≤C.
2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

如果暴力肯定是N^2枚举的。。不过我们可以用一招叫做坐标变换：
我们知道，曼哈顿距离为|X-x|+|Y-Y|
那么由于是绝对值 我门讨论一下
X-x+Y-y=(X+Y)-(x+y)
X-x+y-Y=(X-Y)-(x-y)
x-X+Y-y=-( (X-Y)-(x-y) )
x-X+y-Y=-( (X+Y)-(x+y) )
一共这样四种情况 答案是：max(|(X+Y)-(x+y)|,|(X-Y)-(x-y)|)
如果我们设x’=x+y y’=x-y 答案就变成了max(X’-x’,Y’-y’) 喜闻乐见的排序降维形式
按照x’排序 排序后维护一个类似队列的东西 保证队列内元素x’值相差不超过c
然后搞一个平衡树 以Y’为关键字 每次选择新加入的前驱和后继来维护并查集（然而我set过了treap莫名挂了）
不用担心y’重复的问题 因为一个点只需要一条边就能加入到那个联通块中 一个点如果能加的话必定有一条边。

先这样 晚上回来再继续更。。。
然而这个题还是比较简单的。下面这个就不是这么简单了
[Tjoi 2013]松鼠聚会
有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

马勒基这怎么做 这是啥表示方法。。。d(i,j)=max(|xi-xj|,|yi-yj|)
怎么搞。。。百度了下 这叫切比雪夫距离 如果转化成曼哈顿距离的话需要这样：
令x’=(x+y)/2 y’=(x-y)/2 然后就成了曼哈顿距离。。
好坑 这什么鬼== 其实就是把x轴y轴转了45度 然后再除2 就成了曼哈顿距离。。。

还是不懂。。继续百度。。。。终于 在百度的角落里。我们发现了神级公式。。。
max(a,b)=(a+b)/2+|(a-b)/2|;
max(|a|,|b|)=|(a+b)/2|+|(a-b)/2|;
这是非常重要的一个东西 别问我怎么证明 好像证明就是从上面的切比雪夫距离转曼哈顿距离那里来的。。。
我们可以偷一下前人智慧的结晶。。。。这玩意可以去掉max符号简直神。。
神TM公式：
max(|xi-xj|,|yi-yj|)=|(xi-xj+yi-yj)/2|+|(xi-xj-yi+yj)/2|;
然后又是曼哈顿距离的那一套了
令x’=x+y y’=x-y
2*dist(i,j)=|xi’-xj’|+|yi’-yj’| 这里为了避免double掉精度 最后除2
2*Σdist(i,j)=Σ|xi’-xj’|+Σ|yi’-yj’| x,y分开统计 想办法O(N)求出每个人到其他人的距离就行
这题成功转化为了bzoj1679 只不过这题每个人和每个人都是不一样的 我们需要前缀和后缀都算一遍。。。
最后取个MAX。

还有一道比较简单的：3210: 花神的浇花集会
这个把x,y分别排序找个中位数就行（中位数的话保证了到其他的最近）