题目大意：给定一个二元组集合A{<a, b>}， 一个三元组集合B{<c, d, e>}， 定义 C 为 A 和 B 在 {b = e} 上的连接，求 C 集合中凸点的个数，即：最值点的个数。
题解：
C 为一个三元组集合，求凸点的个数问题等价于三维偏序问题，去重之后可以直接计算。
不过，发现若直接暴力进行连接运算，最坏情况下会产生 (O(NM)) 个 C 元组，时间和空间无法承受。发现对于 A 中同一个 b 值的所有二元组来说，只有最大的 a 值才可能对答案产生贡献。因此，考虑对于每一个 b，都找到一个最大的 a 以及对应元组的数量。这样，对于每一个 B 中的元组来说，至多只有一个 A 中的元组与之对应，即：C 中的合法元素至多只有 (O(M)) 个，答案的上界也是 M。
本题中的 c, d 值域较小，因此，可以直接利用二维树状数组进行维护，即：对 a 排序，并用树状数组维护 c, d 即可。
注意：三位偏序问题一定要去重。
代码如下
#include <bits/stdc++.h>
using namespace std;
struct A {
int a, b;
};
struct B {
int c, d, e;
};
struct C {
int a, c, d, cnt;
C(int x, int y, int z, int w) {
a = x, c = y, d = z, cnt = w;
}
friend bool operator==(const C &x, const C &y) {
return x.a == y.a && x.c == y.c && x.d == y.d;
}
};
struct fenwick {
vector<vector<int>> t;
int n;
fenwick(int _n) {
n = _n;
t.resize(_n + 1, vector<int>(_n + 1));
}
void modify(int x, int y, int val) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= n; j += j & -j) {
t[i][j] += val;
}
}
}
int query(int x, int y) {
int ret = 0;
for (int i = x; i; i -= i & -i) {
for (int j = y; j; j -= j & -j) {
ret += t[i][j];
}
}
return ret;
}
int get(int x, int y) {
return query(n, n) - query(n, y - 1) - query(x - 1, n) + query(x - 1, y - 1);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T, kase = 0;
cin >> T;
while (T--) {
int n, m, range = 0, fen_size = 0;
cin >> n >> m;
vector<A> a(n); // a, b
vector<B> b(m); // c, d, e
for (int i = 0; i < n; i++) {
cin >> a[i].a >> a[i].b;
range = max(range, a[i].b);
}
for (int i = 0; i < m; i++) {
cin >> b[i].c >> b[i].d >> b[i].e;
range = max(range, b[i].e);
fen_size = max(fen_size, max(b[i].c, b[i].d));
}
vector<pair<int, int>> maxa(range + 1); // maxa, cnt
for (int i = 0; i < n; i++) {
if (a[i].a > maxa[a[i].b].first) {
maxa[a[i].b].first = a[i].a;
maxa[a[i].b].second = 1;
} else if (a[i].a == maxa[a[i].b].first) {
maxa[a[i].b].second++;
}
}
vector<C> all, valid;
for (int i = 0; i < m; i++) {
if (maxa[b[i].e].second != 0) {
all.emplace_back(maxa[b[i].e].first, b[i].c, b[i].d, maxa[b[i].e].second);
}
}
sort(all.begin(), all.end(), [&](const C &x, const C &y) {
return x.a == y.a ? x.c == y.c ? x.d > y.d : x.c > y.c : x.a > y.a;
});
valid.emplace_back(all.front());
for (int i = 1; i < (int)all.size(); i++) {
if (all[i] == valid.back()) {
valid.back().cnt += all[i].cnt;
} else {
valid.emplace_back(all[i]);
}
}
int ans = 0;
fenwick t(fen_size);
for (int i = 0; i < (int)valid.size(); i++) {
if (t.get(valid[i].c, valid[i].d) == 0) {
ans += valid[i].cnt;
}
t.modify(valid[i].c, valid[i].d, 1);
}
cout << "Case #" << ++kase << ": " << ans << endl;
}
return 0;
}