Problem: BOJ 17131 — Reason the fox came up to Island · 한국어 · 日本語
For a point to be the middle point of a fox triple, one point must lie strictly to its left and another strictly to its right, and both of those points must have a greater y coordinate. For a middle point p, let L(p) and R(p) be the numbers of eligible points on its left and right. It contributes L(p) * R(p) triples. Every choice of one point from each side gives one triple, so summing these products counts every triple exactly once.
Sort the points by x and process all points with the same x as one group. Before inserting a group into the Fenwick tree, query every point in it; thus the tree contains only points with strictly smaller x. Repeat in reverse for the right side. Delaying updates until the whole group has been queried excludes points with equal x in both sweeps. Each input point is a separate record, so duplicate coordinates are counted as distinct points.
Compress the input y coordinates to ranks. For a point of rank r, the number of already processed points with strictly greater y is total - prefix(r), where prefix(r) includes rank r; this excludes equal y. Compression also handles the full coordinate range without an arbitrary offset. The two sweeps take O(N log N) time and O(N) space. Counts and products use long long, and the accumulated answer is reduced modulo 1,000,000,007.
C++
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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
constexpr long long MOD = 1'000'000'007LL;
struct Point {
int x;
int y;
int rank;
long long left = 0;
long long right = 0;
};
class Fenwick {
public:
explicit Fenwick(int n) : tree(n + 1, 0) {}
void add(int index) {
for (int i = index; i < static_cast<int>(tree.size()); i += i & -i) {
++tree[i];
}
}
long long prefixSum(int index) const {
long long result = 0;
for (int i = index; i > 0; i -= i & -i) result += tree[i];
return result;
}
private:
vector<long long> tree;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Point> points(n);
vector<int> ys;
ys.reserve(n);
for (Point &point : points) {
cin >> point.x >> point.y;
ys.push_back(point.y);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for (Point &point : points) {
point.rank = lower_bound(ys.begin(), ys.end(), point.y) - ys.begin() + 1;
}
sort(points.begin(), points.end(),
[](const Point &a, const Point &b) { return a.x < b.x; });
Fenwick bit(static_cast<int>(ys.size()));
long long total = 0;
for (int first = 0; first < n;) {
int last = first;
while (last < n && points[last].x == points[first].x) ++last;
for (int i = first; i < last; ++i) {
points[i].left = total - bit.prefixSum(points[i].rank);
}
for (int i = first; i < last; ++i) {
bit.add(points[i].rank);
++total;
}
first = last;
}
bit = Fenwick(static_cast<int>(ys.size()));
total = 0;
for (int last = n; last > 0;) {
int first = last - 1;
while (first > 0 && points[first - 1].x == points[last - 1].x) --first;
for (int i = first; i < last; ++i) {
points[i].right = total - bit.prefixSum(points[i].rank);
}
for (int i = first; i < last; ++i) {
bit.add(points[i].rank);
++total;
}
last = first;
}
long long answer = 0;
for (const Point &point : points) {
answer = (answer + point.left * point.right) % MOD;
}
cout << answer << '\n';
}