容易转化成经典的有向图博弈模型。每张牌建一个点，若 \(x\) 能打败 \(y\) 就连一条 \(x \to y\) 的边。入度为 \(0\) 的点为必败态，之后类似拓扑排序倒推即可。
具体就是若存在边 \(u \to v\)，若 \(u\) 为必败态则 \(v\) 为必胜态并加入队列；若 \(v\) 的所有前驱都是必胜态，那么 \(v\) 为必败态并加入队列。最后没考虑到的点即为平局态。有点类似 P9169 [省选联考 2023] 过河卒。
朴素地做边数 \(O(n^2)\)，无法承受。注意到若把双方的牌都按防御值排序，那么一个点的出边是一段连续的区间。设点 \(u\) 的连边区间为 \([l_u, r_u]\)。于是可以直接线段树维护每个点的入度，每当入度最小值为 \(0\) 就把对应的点 push 进队列并将这个点的状态设为必败态。线段树需要支持区间加，单点修改，查全局最小值及其位置。
还需要支持当 \(u\) 为必败态时把 \(u\) 的所有后继都设为必胜态。发现实际上进行操作的只有 \(u\) 的之前没设为必胜态的后继的点。套路地使用并查集，并查集上每个点的祖先为它下一个还没被设为必胜态的点，就可以暴力找到要更新的点了。
时间复杂度 \(O((n + m) \log (n + m))\)。
code
// Problem: E. Infinite Card Game
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/E
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 1000100;
int n, m, f[maxn], fa[maxn];
pii g[maxn];
struct node {
int x, y;
} a[maxn], b[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
namespace SGT {
pii a[maxn << 2];
int tag[maxn << 2];
inline void pushup(int x) {
a[x] = min(a[x << 1], a[x << 1 | 1]);
}
inline void pushdown(int x) {
if (!tag[x]) {
return;
}
a[x << 1].fst += tag[x];
a[x << 1 | 1].fst += tag[x];
tag[x << 1] += tag[x];
tag[x << 1 | 1] += tag[x];
tag[x] = 0;
}
void build(int rt, int l, int r) {
tag[rt] = 0;
if (l == r) {
a[rt] = mkp(0, l);
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int ql, int qr, int x) {
if (ql > qr) {
return;
}
if (ql <= l && r <= qr) {
a[rt].fst += x;
tag[rt] += x;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (ql <= mid) {
update(rt << 1, l, mid, ql, qr, x);
}
if (qr > mid) {
update(rt << 1 | 1, mid + 1, r, ql, qr, x);
}
pushup(rt);
}
void modify(int rt, int l, int r, int x) {
if (l == r) {
a[rt].fst = 1e9;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
(x <= mid) ? modify(rt << 1, l, mid, x) : modify(rt << 1 | 1, mid + 1, r, x);
pushup(rt);
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].x);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].y);
}
scanf("%d", &m);
for (int i = 1; i <= m; ++i) {
scanf("%d", &b[i].x);
}
for (int i = 1; i <= m; ++i) {
scanf("%d", &b[i].y);
}
sort(a + 1, a + n + 1, [&](const node &a, const node &b) {
return a.y < b.y;
});
sort(b + 1, b + m + 1, [&](const node &a, const node &b) {
return a.y < b.y;
});
SGT::build(1, 1, n + m);
for (int i = 1; i <= n; ++i) {
int l = 1, r = m, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[i].x > b[mid].y) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
g[i] = mkp(n + 1, n + pos);
SGT::update(1, 1, n + m, g[i].fst, g[i].scd, 1);
}
for (int i = 1; i <= m; ++i) {
int l = 1, r = n, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (b[i].x > a[mid].y) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
g[i + n] = mkp(1, pos);
SGT::update(1, 1, n + m, g[i + n].fst, g[i + n].scd, 1);
}
static int q[maxn];
int hd = 1, tl = 0;
for (int i = 1; i <= n + m; ++i) {
f[i] = -1;
fa[i] = i;
}
fa[n + m + 1] = n + m + 1;
while (SGT::a[1].fst == 0) {
int u = SGT::a[1].scd;
f[u] = 0;
q[++tl] = u;
SGT::modify(1, 1, n + m, u);
}
while (hd <= tl) {
int u = q[hd++];
if (f[u] == 0) {
for (int i = find(g[u].fst); i <= g[u].scd; i = find(i + 1)) {
f[i] = 1;
q[++tl] = i;
fa[i] = i + 1;
}
}
SGT::update(1, 1, n + m, g[u].fst, g[u].scd, -1);
while (SGT::a[1].fst == 0) {
int v = SGT::a[1].scd;
SGT::modify(1, 1, n + m, v);
if (f[v] == -1) {
f[v] = 0;
q[++tl] = v;
}
}
}
int c1 = 0, c2 = 0, c3 = 0;
for (int i = 1; i <= n; ++i) {
if (f[i] == 0) {
++c1;
} else if (f[i] == -1) {
++c2;
} else {
++c3;
}
}
printf("%d %d %d\n", c1, c2, c3);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}