自动搬运

查看原文

来自洛谷，原作者为

	fzitb7912 worio，磨灭，依靠。

搬运于2025-08-24 23:05:09，当前版本为作者最后更新于2024-10-17 14:27:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解摘自 CSP2024 前做题情况。

参考文献，云浅老师好强。 /bx/bx/bx

分析

发现条件 $1$ 没有什么用。令 $a_i$ 为 $i$ 在 $P(1)$ 中的位置；$b_i$ 为 $i$ 在 $P(2)$ 中的位置；$c_i$ 为 $i$ 在 $P(3)$ 中的位置。若满足 $a_i < a_j \land b_i < b_j \land c_i <c_j$，且 $T$ 中 $i$ 在 $j$ 前面，则满足条件。若此时 $T$ 中 $i$ 在 $j$ 后面，那么就可以把 $i,j$ 交换一下，也满足条件。

所以原题就是求满足：$a_i <a_j\land b_i < b_j\land c_i<c_j$ 的二元组 $(i,j)$ 的数量。这是一个三位偏序的板子，使用 CDQ 分治可以做到 $O(n \log^2 n)$。需要细微卡常，但是能过。

在这里介绍一下时间复杂度为 $O(n\log n)$ 的算法。该算法带了一个 $3$ 倍的常数，不过不影响。我们考虑把一个三维偏序问题转化为 $3$ 个二维偏序问题的交。令 $S_1=\{(i,j)|a_i<a_j\},S_2=\{(i,j)|b_i<b_j\},S_3=\{(i,j)|c_i<c_j\}$。那么有答案集合 $S=S_1\cap S_2\cap S_3$，则 $(i,j)$ 的数量为 $|S_1\cap S_2\cap S_3|$。根据容斥有：$|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-|S_1\cup S_2\cup S_3|}{2}$。其中 $S_1,S_2,S_3$ 分别能够算出来，难点在于维护 $|S_1\cup S_2\cup S_3|$。这里需要一点注意力。

对于一对 $(i,j)$，我们会发现若它们满足一维偏序，则 $(j,i)$ 满足二维偏序；若它们满足二维偏序，则 $(j,i)$ 满足一维偏序；若它们满足三维偏序，则 $(j,i)$ 不满足任何偏序。而 $S_1,S_2,S_3$ 中任何一对 $(i,j)$ 至少满足二维偏序。所以 $|S_1\cup S_2\cup S_3|$ 刚好是无序二元组 $(i,j)$ 的数量，即 $\frac{n\times (n-1)}{2}$。

所以原式子可以写成：$|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-\frac{n\times(n-1)}{2}}{2}$。所以只需要算出来 $|S_1\cap S_2|,|S_2\cap S_3|,|S_3\cap S_1|$ 就能求解三维偏序问题了。时间复杂度 $O(n\log n)$。

代码

il void solve(){
	n=rd;int ans=0;
	for(re int i=1;i<=n;++i) rd;
	for(re int i=1;i<=n;++i) a[rd]=i;
	for(re int i=1;i<=n;++i) b[rd]=i;
	for(re int i=1;i<=n;++i) c[rd]=i;
	
	for(re int i=1;i<=n;++i) d[a[i]]=b[i];
	for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
	for(re int i=1;i<=n;++i) tr[i]=0;

	for(re int i=1;i<=n;++i) d[b[i]]=c[i];
	for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
	for(re int i=1;i<=n;++i) tr[i]=0;

	for(re int i=1;i<=n;++i) d[c[i]]=a[i];
	for(re int i=1;i<=n;++i) ans+=query(d[i]),add(d[i],1);
	for(re int i=1;i<=n;++i) tr[i]=0;
	
	printf("%lld\n",(ans-n*(n-1)/2)/2);	
	return ;
}