POJ 3244 Difference between Triplets 题解：（线段树或树状数组）或（排序 + 前缀和）

坠痛苦的是，POJ 的辣鸡 G++ 编译器不支持 long long，害得我调试调了半天……

Description

For every pair of triplets, $T_a = (I_a, J_a, K_a)$ and $T_b = (I_b, J_b, K_b)$, we define the difference value between $T_a$ and $T_b$ as follows:

$D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b)$

Now you are given $N$ triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

Input

The input consists of several test cases. Each test case begins with a line containing an integer $N$, denotes the number of triplets. Assume that we number the triplets as $T_1, T_2, \dots , T_N$. Then, there are following $N$ lines, each line contains three integers, giving the elements of each triplet. A case with $N = 0$ indicates the end of the input.

Sample Input

2
1 2 3
3 2 1
3
1 3 2
4 0 7
2 2 9
0

Sample Output

4
20

Hint

Case 1: $D(T_1,T_2)=4$ Case 2: $D(T_1,T_2)+D(T_1,T_3)+D(T_2,T_3)=8+8+4=20$

You can assume that $N$, the number of triplets in each case, will not exceed 200,000 and the elements in triplets fit into $[-10^6,10^6]$. The size of the input will not exceed 5 MB.

Analysis

Solutoin #1

很类似上次的HDU 5626 Clarke and points和HDU 6447 YJJ’s Salesman的结合，我们可以先分类讨论（因为这是一个轮换对称式，其实随便考虑一种情况就可以了）。

假设 $\max (I_a − I_b, J_a − J_b, K_a − K_b) = I_a - I_b$，那么就有：

$I_a-I_b>J_a-J_b,I_a-I_b>K_a-K_b$

变换得到：

$I_a-J_a>I_b-J_b,I_a-K_a-i_b-K_b$

令 $A_i=I_i-J_i,B_i=I_i-K_i$，显然 $A_i>A_j,B_i>B_j$。 这就转换成区间选点问题了。只需要先按照 $A_i$ 排序，然后用线段树或者树状数组维护下就可以了～

Solution #2

上面的解法显然太麻烦了，其实有一种更加精妙的做法。

首先我们要知道一个超级重要的公式：

$\max(a,b,c)-\min(a,b,c) = \frac {|a-b|+|b-c|+|c-a|} 2$

所以可以得到：