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

This blog post is only available in Simplified Chinse.

坠痛苦的是，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

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$

所以可以得到：

= \frac {|I_a-I_b-J_a+J_b| + |J_a-J_b-K_a-K_b| + |K_a-K_b-I_a+I_b|} 2 $$ 同样令 $A_i=I_i-J_i,B_i=J_i-K_i,C_i=K_i-A_i$，整理得到： $$ D(T_a,T_b)=\frac {|A_a-A_b|+|B_a-B_b|+|C_a-C_b|} 2 $$ 所以只需要对于每个 $A_i$，累计它与所有小于它的 $A_i$ 之差之和，对于 $B_i$ 和 $C_i$ 同理。即： $$\sum D(T_i,T_j) = \frac {\sum_{A_i< A_j} (A_j-A_i) +\sum_{C_i< C_j} (C_j-C_i) + \sum_{C_i< C_j} (C_j-C_i) } {2} $$ 这个很好做，维护下加和就好了。 ## Code ~~第一种解法代码懒得写了……~~ \下面是解法二的代码。**POJ 这题提交的时候如果语言选择 G++ 会 WA 掉，但是用 C++ 就过了……**困扰了我很长时间…… 嗯，原来在 FAQ 里面说了： > Prior to the compiler upgrade in May 2009, we serviced C and C++ submissions using GCC 3.4.2. That version of GCC relies on the old MS VC++ 6 runtime library, which does not support the `%lld` and `%llu` specifiers for signed and unsigned `long long` types but allows the standard-incompliant `%lf` and `%lg` specifiers for floating-point types. The new GCC 4.4.0 comes with its own ISO C-conformant implementation of the printf function. Now you can use `%lld` and `%llu` with either C/C++ compiler, but `%lf` and `%lg` only work with MS VC++ 2008 Express. As a rule of thumb, you should always use the `%f` and `%g` specifiers instead for floating-point types. …可怕…… ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const long long maxn=200005; long long n,a[maxn],b[maxn],c[maxn]; long long ans=0; int main(){ for (;;){ scanf("%lld",&n); if (n==0) break; ans=0; for (long long i=1;i<=n;i++){ long long x,y,z; scanf("%lld%lld%lld",&x,&y,&z); a[i]=x-y,b[i]=y-z,c[i]=z-x; } sort(a+1,a+1+n);sort(b+1,b+1+n);sort(c+1,c+1+n); long long sum_a=0,sum_b=0,sum_c=0; for (long long i=1;i<=n;i++){ ans+=a[i]*(i-1)-sum_a; ans+=b[i]*(i-1)-sum_b; ans+=c[i]*(i-1)-sum_c; sum_a+=a[i];sum_b+=b[i];sum_c+=c[i]; } printf("%lld\n",ans/2); } return 0; } ```

9/11/2018