|
|
题目链接：http://poj.org/problem?id=3067
  /**//*
 题意：
左边N个点，右边M个点，分别南北方向排列，1对应1，2对应2，给出
K条记录，每条记录表示左边的A点和右边的B点相连，两条相连的先会有一
个交点，现在保证任意三个线不会交与一点，问一共多少个交点。
题解：
树状数组
思路：
题目求的是交点的数目，仔细观察就可以发现，如果有以下四个点，A1
，B1属于左边，A2，B2属于右边，当且仅当 A1和A2的大小关系 和 B1与B2
的大小关系 相反，于是可以联想到求一个数列的逆序数的时候用到的树状数
组的成段求和。
我们只要将读入的整数对按左边的点递增排序，如果左边点大小相同则按
右边点递增排序，每次在树状数组中统计比当前右边的点大的数的数目，然后
再将这个点插入树状数组，这就实现了一个逆序统计。
这里需要注意的是，统计的时候需要采用__int64，因为总的交点数可能
会超过int。最大的情况是左右两边都是1000个点，并且两两有边，那么最大
的交点数量就是：
1 * (1 + 2 +  + 999)
+
2 * (1 + 2 + + 998)
+
998 * (1 + 2)
+
999 * 1
+
1000 * 0
可以写个程序统计一下，发现这个数字是超过int的。
ll ans = 0;
for(i = 1; i <= 1000; i++) {
ans += i * (1001 - i) * (1000 - i) / 2;
}
 */
#include <iostream>
#include <algorithm>
using namespace std;
struct Double {
int l, r;
}dt[1000100];
int N, M, K;
#define ll __int64
int cmp(Double a, Double b) {
if(a.l == b.l)
return a.r < b.r;
return a.l < b.l;
}
int lowbit(int x) {
return x & (-x);
}
ll c[1010];
void add(int pos) {
  while(pos <= M) {
c[pos] ++;
pos += lowbit(pos);
 }
}
ll sum(int pos) {
ll s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int main() {
int t;
int i;
int Case = 1;
scanf("%d", &t);
while(t--) {
memset(c, 0, sizeof(c));
scanf("%d %d %d", &N, &M, &K);
for(i = 0; i < K; i++) {
scanf("%d %d", &dt[i].l, &dt[i].r);
}
sort(dt, dt + K, cmp);
ll ans = 0;
for(i = 0; i < K; i++) {
ans += sum(M) - sum(dt[i].r);
add(dt[i].r);
}
printf("Test case %d: %I64d\n", Case++, ans);
}
return 0;
}
|