PKU 3067 Japan
英雄哪里出来发表于 2011-04-08 15:14:00
题目链接：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;
}
/**//*题意： 左边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 __int64int 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;}