思路：
開(kāi)四個(gè)樹(shù)狀數(shù)組。。
arr_x，arr_y，arr_xy，arr_cnt
分別統(tǒng)計(jì)y軸下：x的和、y的和、x*y的和、點(diǎn)的個(gè)數(shù)。
把點(diǎn)按照x排序，x越大的點(diǎn)出現(xiàn)得越晚。
從前往后推，每出現(xiàn)一個(gè)新的點(diǎn)的時(shí)候：
Step1，將該點(diǎn)加入到四個(gè)數(shù)組中。
Step2，對(duì)于高于它的點(diǎn)，面積增量為 x*sum(y) - sum(x*y)。
Step3，對(duì)于低于它的點(diǎn)，面積增量為 sum(y) * (cnt * x - sum(x))
最終得出結(jié)果。復(fù)雜度O(NlgN)。代碼 63ms。
注意：
需要用int64保存數(shù)組元素
#include <stdio.h>
#define MAX_X 20032
#define MAX_Y 20032
int cow[MAX_X], left, top, N;
__int64 arr_x[MAX_Y], arr_y[MAX_Y], arr_xy[MAX_Y], arr_cnt[MAX_Y];
__inline int lowbit(int i)
{
return i & (i ^ (i - 1));
}
__inline __int64 sum(__int64 *arr, int i)
{
__int64 s;
for (s = 0; i; i -= lowbit(i))
s += arr[i];
return s;
}
__inline void insert(__int64 *arr, int i, __int64 val)
{
for (; i <= top; i += lowbit(i))
arr[i] += val;
}
int main()
{
int i, x, y;
__int64 s, sx, sy, sxy, c;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
left = MAX_X;
for (i = 0; i < N; i++) {
scanf("%d%d", &y, &x);
if (x < left)
left = x;
if (y > top)
top = y;
cow[x] = y;
}
s = 0;
x = left - 1;
for (i = 0; i < N; i++) {
for (x++; !cow[x]; x++);
y = cow[x];
insert(arr_x, y, x);
insert(arr_y, y, y);
insert(arr_xy, y, x * y);
insert(arr_cnt, y, 1);
c = sum(arr_cnt, y - 1);
sx = sum(arr_x, y - 1);
s += c*x*y - sx*y;
sy = sum(arr_y, top) - sum(arr_y, y - 1);
sxy = sum(arr_xy, top) - sum(arr_xy, y - 1);
s += x*sy - sxy;
}
printf("%I64d\n", s);
return 0;
}