Problem: BOJ 5419 — Northwesterly Wind · 한국어 · 日本語
For each test case, count pairs of points (x1, y1) and (x2, y2) satisfying x1 <= x2 and y1 >= y2. A pair is counted once in the left-to-right sweep order. Thus, points with the same x-coordinate are ordered by decreasing y, and identical points contribute one pair for each choice of two copies.
Sort points by x ascending, then y descending. This order ensures that when a point is processed, every previously processed point has x <= its x-coordinate. For equal x, larger y comes first, so a previously processed point also has y >= the current y. This handles equal x without separately grouping points and counts duplicate points as distinct input points.
Compress all y-coordinates to ranks 1..K in increasing order. A Fenwick tree stores how many processed points have each rank. For current rank r, query the suffix sum from r through K: it counts all earlier points whose y-coordinate is at least the current y. Add that count to a long answer, then insert the current point. Querying before insertion ensures that a point is never paired with itself.
The algorithm sorts and compresses in O(N log N) time; each of the N Fenwick queries and updates also takes O(log N). Total time is O(N log N) and auxiliary space is O(N). The answer uses long because up to N(N - 1) / 2 pairs may be counted.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
private static final class Point {
final int x;
final int y;
int yRank;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private static final class FenwickTree {
private final int[] tree;
FenwickTree(int size) {
tree = new int[size + 1];
}
void add(int index) {
for (int i = index; i < tree.length; i += i & -i) {
tree[i]++;
}
}
int prefixSum(int index) {
int sum = 0;
for (int i = index; i > 0; i -= i & -i) {
sum += tree[i];
}
return sum;
}
}
private static final class FastScanner {
private final BufferedReader reader =
new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer tokens;
int nextInt() throws IOException {
while (tokens == null || !tokens.hasMoreTokens()) {
tokens = new StringTokenizer(reader.readLine());
}
return Integer.parseInt(tokens.nextToken());
}
}
public static void main(String[] args) throws Exception {
FastScanner input = new FastScanner();
int testCases = input.nextInt();
StringBuilder output = new StringBuilder();
while (testCases-- > 0) {
int n = input.nextInt();
Point[] points = new Point[n];
int[] ys = new int[n];
for (int i = 0; i < n; i++) {
int x = input.nextInt();
int y = input.nextInt();
points[i] = new Point(x, y);
ys[i] = y;
}
Arrays.sort(ys);
int uniqueCount = 0;
for (int y : ys) {
if (uniqueCount == 0 || ys[uniqueCount - 1] != y) {
ys[uniqueCount++] = y;
}
}
for (Point point : points) {
point.yRank = Arrays.binarySearch(ys, 0, uniqueCount, point.y) + 1;
}
Arrays.sort(points, Comparator
.comparingInt((Point point) -> point.x)
.thenComparing(Comparator.comparingInt((Point point) -> point.y).reversed()));
FenwickTree fenwick = new FenwickTree(uniqueCount);
long answer = 0;
for (Point point : points) {
int lessThanY = fenwick.prefixSum(point.yRank - 1);
int atLeastY = fenwick.prefixSum(uniqueCount) - lessThanY;
answer += atLeastY;
fenwick.add(point.yRank);
}
output.append(answer).append('\n');
}
System.out.print(output);
}
}