容斥思想辅助mex计数+CDQ分治：26暑杭电 3-11

1011 Mex

感觉这道题最巧妙的地方是，用每个位置 ii 去计算对答案的贡献。

也就是钦定0、1、2、3个为位置为mex，然后用容斥计算是否可行

0个位置的贡献为1（即全选）

1个位置的话有 nn 种，而且显然合法

2个位置，有 (n2)\binom n 2 种。不合法的情况是形成三维偏序。

3个位置，有 (n3)\binom n 3 种，不合法的情况是形成二维偏序，根据容斥，要加回三维偏序。

image-20260802113413726

于是总方案为：

1+n+(n2)−∑iABC(i)+(n3)−∑i((AB(i)2)+(AC(i)2)+(BC(i)2)−2(ABC(i)2))1+n+\binom n 2 -\sum_iABC(i)+\binom n 3-\sum_i\left(\binom{AB(i)}2+\binom{AC(i)}2+\binom{BC(i)}2-2\binom{ABC(i)}2\right)

三维偏序直接拿cdq算即可。

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
struct node {
	int a, b, c, i; 
	void clear() {
		a = b = c = i = 0; 
	}
}a[N], ax[N]; 
int n, m, i, j, k, T;
int AB[N], AC[N], BC[N], ABC[N]; 
int ans; 

struct Binary_tree {
	int cnt[N], i; 
	void clear() {
		for(i = 0; i <= n; ++i) cnt[i] = 0; 
	}
	void add(int x, int y) {
		while(x <= n) {
			cnt[x] += y; 
			x += x & -x; 
		}
	}
	int qry(int x) {
		int ans = 0; 
		while(x) {
			ans += cnt[x]; 
			x -= x & -x; 
		}
		return ans; 
	}
}Bin;

void CDQ(int l, int r) {
//	debug("[%lld %lld]\n", l, r); 
	if(l == r) return ; 
	int mid = (l + r) >> 1; 
	CDQ(l, mid); CDQ(mid + 1, r); 
	int i, j, k; 
	for(i = k = l, j = mid + 1; i <= mid || j <= r; ++k) {
//		debug("Now %lld %lld\n", i, j); 
		if(i <= mid && (j > r || a[i].b > a[j].b)) {
			ABC[a[i].i] += j - mid - 1 - Bin.qry(a[i].c); 
			ax[k] = a[i]; ++i; 
		}
		else {
			Bin.add(a[j].c, 1); 
			ax[k] = a[j]; ++j; 
		}
	}
	for(i = mid + 1; i <= r; ++i) Bin.add(a[i].c, -1); 
	for(i = l; i <= r; ++i) a[i] = ax[i];  
}

void init() {
	for(i = 0; i <= n + 1; ++i) {
		a[i].clear(); ax[i].clear(); 
		AB[i] = AC[i] = BC[i] = ABC[i] = 0; 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		n = read(); 
		init(); 
		for(i = 1; i <= n; ++i) a[i].i = i; 
		for(i = 1; i <= n; ++i) a[i].a = read() + 1; 
		for(i = 1; i <= n; ++i) a[i].b = read() + 1; 
		for(i = 1; i <= n; ++i) a[i].c = read() + 1; 
		sort(a + 1, a + n + 1, [] (node x, node y) { return x.a > y.a; }); 
		for(i = 1, Bin.clear(); i <= n; ++i) {
			AB[a[i].i] = i - 1 - Bin.qry(a[i].b); 
			Bin.add(a[i].b, 1); 
		}
		sort(a + 1, a + n + 1, [] (node x, node y) { return x.a > y.a; }); 
		for(i = 1, Bin.clear(); i <= n; ++i) {
			AC[a[i].i] = i - 1 - Bin.qry(a[i].c); 
			Bin.add(a[i].c, 1); 
		}
		sort(a + 1, a + n + 1, [] (node x, node y) { return x.b > y.b; }); 
		for(i = 1, Bin.clear(); i <= n; ++i) {
			BC[a[i].i] = i - 1 - Bin.qry(a[i].c); 
			Bin.add(a[i].c, 1); 
		}
		sort(a + 1, a + n + 1, [] (node x, node y) { return x.a < y.a; }); 
		Bin.clear(); CDQ(1, n); 
		sort(a + 1, a + n + 1, [] (node x, node y) { return x.i < y.i; }); 
		for(i = 1; i <= n; ++i) debug("%lld ", AB[i]); debug("\n"); 
		for(i = 1; i <= n; ++i) debug("%lld ", AC[i]); debug("\n"); 
		for(i = 1; i <= n; ++i) debug("%lld ", BC[i]); debug("\n"); 
		for(i = 1; i <= n; ++i) debug("%lld ", ABC[i]); debug("\n"); 
		ans = 1 + n; 
		auto C2 = [&] (int n) -> int {
			return n * (n - 1) / 2; 
		}; 
		auto C3 = [&] (int n) -> int {
			return n * (n - 1) * (n - 2) / 6; 
		}; 
		auto Add = [&] (int &a, int b) -> void {
			a += b; 
		}; 
		Add(ans, C2(n)); 
		for(i = 1; i <= n; ++i) Add(ans, -ABC[i]); 
		Add(ans, C3(n)); 
		for(i = 1; i <= n; ++i) {
			Add(ans, -C2(AB[i])); 
			Add(ans, -C2(AC[i])); 
			Add(ans, -C2(BC[i])); 
			Add(ans, 2 * C2(ABC[i])); 
		}
		printf("%lld\n", ans);
	}

	return 0;
}