POJ 3067 Japan(樹状配列求逆順対)

ジャパン
http://poj.org/problem?id=3067
Time Limit:
 1000 MS
メモリLimit: 65536 K
Description
Japan plans to welcome the ACM ICPC World Finals and a lot of roads must be built for the ventue.Japan is tall island with N cities on the East and M cities on the West coast(M==1000,N==1000)K perhibusityle.K.Centfrom North to South.Each superhighway isststrarainind and connects city on the East coast with city of the West coast.The funding for the constststrution isgarted by ACM.A majorpotion of the sususum dedededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededededete a program that cacaculates the number of the crossings between superhighways.
Input
The input file starts with T-the number of test cases.Each test case starts with th three numbers–N,M,K.Each of the next Kオンラインオンラインオンラインオンラインs twonumbes–thenumbes of citicontenected bythe superhigwarsthe the the the the the the the thethethethethethethe superhigggwawawawawarss s s s s s s s s s s s s s s thethethethethethethethethethethethethe thethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethe st coast.
Output
For each test case write one line on the standar output: 
Test case(case number):(number of crossings)
Sample Input

1
3 4 4
1 4
2 3
3 2
3 1

Sample Output

Test case 1: 5

題意抽象:
二分割図(偶数図)G＜V、E＞の二部を(V 1、V 2)、124 V 1 124＝N、124 V 2 124＝M、124 E 124＝Kに区分する.V 1とV 2の上の点をすでに知っていて、それぞれ2本の平行線の上で、点と点の間はまっすぐにつながっています.そして各交点は最大で2本の直線の上で、交点の個数を求めます.
解法:
複雑度:
1.2点セットの要素の並べ替え、優先度V 1>V 2

const int MAXN = 1002;

struct Node {
		int a, b;
} node[MAXN * MAXN];

bool cmp(Node a, Node b) {
	return a.a != b.a ? a.a < b.a : a.b < b.b;
}

sort(node + 1, node + 1 + K, cmp);

2.そして順次に接続線を追加し、V 2端がbより大きい点の個数を同時に統計する.注意と値が大きいので、long longを使います.

int lowbit(int x) {
	return -x & x;
}

void add(int i, int val) {
	while (i <= M) {
		c[i] += val;
		i += lowbit(i);
	}
}

int sum(int i) {
	int s = 0;
	while (i) {
		s += c[i];
		i -= lowbit(i);
	}
	return s;
}

long long ans = 0;
add(node[1].b, 1);
for (int i = 2; i <= K; i++) {
	add(node[i].b, 1);
	ans += sum(M) - sum(node[i].b);//   node[i].b     ，O(log M)  
}

完全コード:

/*485ms,2760KB*/

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;

const int MAXN = 1002;
int c[MAXN];
int N, M, K;

struct Node {
		int a, b;
} node[MAXN * MAXN];

bool cmp(Node a, Node b) {
	return a.a != b.a ? a.a < b.a : a.b < b.b;
}

int lowbit(int x) {
	return -x & x;
}

void add(int i, int val) {
	while (i <= M) {
		c[i] += val;
		i += lowbit(i);
	}
}

// i  
int sum(int i) {
	int s = 0;
	while (i) {
		s += c[i];
		i -= lowbit(i);
	}
	return s;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int iCase = 1; iCase <= T; iCase++) {
		scanf("%d%d%d", &N, &M, &K);
		for (int i = 1; i <= K; i++) {
			scanf("%d%d", &node[i].a, &node[i].b);
		}
		///////////////////////
		sort(node + 1, node + 1 + K, cmp); //  
		memset(c, 0, sizeof(c));
		long long ans = 0;
		add(node[1].b, 1);
		for (int i = 2; i <= K; i++) {
			add(node[i].b, 1);
			ans += sum(M) - sum(node[i].b);//   node[i].b     ，O(log M)  
		}
		printf("Test case %d: %I64d
", iCase, ans);
	}
	return 0;
}