|
|
題目鏈接：http://poj.org/problem?id=3067
  /**//*
 題意：
左邊N個點，右邊M個點，分別南北方向排列，1對應(yīng)1，2對應(yīng)2，給出
K條記錄，每條記錄表示左邊的A點和右邊的B點相連，兩條相連的先會有一
個交點，現(xiàn)在保證任意三個線不會交與一點，問一共多少個交點。
題解：
樹狀數(shù)組
思路：
題目求的是交點的數(shù)目，仔細(xì)觀察就可以發(fā)現(xiàn)，如果有以下四個點，A1
，B1屬于左邊，A2，B2屬于右邊，當(dāng)且僅當(dāng) A1和A2的大小關(guān)系 和 B1與B2
的大小關(guān)系 相反，于是可以聯(lián)想到求一個數(shù)列的逆序數(shù)的時候用到的樹狀數(shù)
組的成段求和。
我們只要將讀入的整數(shù)對按左邊的點遞增排序，如果左邊點大小相同則按
右邊點遞增排序，每次在樹狀數(shù)組中統(tǒng)計比當(dāng)前右邊的點大的數(shù)的數(shù)目，然后
再將這個點插入樹狀數(shù)組，這就實現(xiàn)了一個逆序統(tǒng)計。
這里需要注意的是，統(tǒng)計的時候需要采用__int64，因為總的交點數(shù)可能
會超過int。最大的情況是左右兩邊都是1000個點，并且兩兩有邊，那么最大
的交點數(shù)量就是：
1 * (1 + 2 +  + 999)
+
2 * (1 + 2 + + 998)
+
998 * (1 + 2)
+
999 * 1
+
1000 * 0
可以寫個程序統(tǒng)計一下，發(fā)現(xiàn)這個數(shù)字是超過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;
}
|