题目

题目链接：https://www.luogu.com.cn/problem/P1232
我们知道一棵有根树可以进行深度优先遍历（DFS）以及广度优先遍历（BFS）来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同，并且它们的 BFS 序也有可能相同，例如下面两棵树的 DFS 序都是 1 2 4 5 3，BFS 序都是 1 2 3 4 5。

现给定一个 DFS 序和 BFS 序，我们想要知道，符合条件的有根树中，树的高度的平均值。即，假如共有 \(K\) 棵不同的有根树具有这组 DFS 序和 BFS 序，且他们的高度分别是 \(h_1, h_2, \ldots, h_K\)，那么请你输出：

\[\frac{h_1+h_2+\ldots+h_K}K \]

\(n\leq 2\times 10^5\)。

思路

同一深度的点在 BFS 序上肯定是连续的一个区间。所以其实就是求 BFS 序上可以分成的段数的期望 \(+1\)。
利用期望的线性性，分别考虑 BFS 序相邻的两个点之间是必须分段 / 可以分段 / 不能分段。必须分段贡献是 \(1\)，可以分段贡献是 \(0.5\)，不能分段贡献是 \(0\)。

• 必须分段：如果 BFS 序相邻的两个点 \(i,j\) 满足 \(i\) 的 DFS 序小于 \(j\) 的 DFS 序，那么 \(i,j\) 之间可以不分段。转化为逆否命题，如果 BFS 序相邻的两个点之间必须分段，那么一定有 \(i\) 的 DFS 序大于 \(j\) 的 DFS 序。
• 不能分段：考虑 DFS 序对 BFS 序是否分段的影响。如果 DFS 序相邻的两个点 \(i,j\)（那么有 \(\text{dep}_j\leq \text{dep}_i+1\)），满足 \(i\) 的 BFS 序小于 \(j\) 的 BFS 序（那么有 \(\text{dep}_j\geq \text{dep}_i\)），那么 \(\text{dep}_i\leq \text{dep}_j\leq \text{dep}_i+1\)。也就是 BFS 序上 \(i\) 到 \(j\) 这一段区间中，最多有一个位置必须分段。所以在求出所有必须分段的位置后，如果这一段区间之间存在一个必须分段的位置，那么这一段区间剩余的所有位置都不能分段。

可以利用差分来标记每一个位置是否不能分段。
时间复杂度 \(O(n)\)。

其实我没太搞懂为什么这样是充分的。只能感性理解一下。题解区似乎也没有比较完整的证明。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=200010;
int n,id1[N],rk1[N],id2[N],rk2[N],a[N],b[N];
double ans;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&id1[i]),rk1[id1[i]]=i;
	for (int i=1;i<=n;i++)
		scanf("%d",&id2[i]),rk2[id2[i]]=i;
	for (int i=1;i<n;i++)
		b[i]=b[i-1]+(rk1[id2[i]]>rk1[id2[i+1]] || i==1);
	for (int i=1;i<n;i++)
		if (rk2[id1[i]]<rk2[id1[i+1]] && b[rk2[id1[i+1]]-1]-b[rk2[id1[i]]-1])
			a[rk2[id1[i]]]++,a[rk2[id1[i+1]]]--;
	for (int i=1;i<n;i++)
	{
		a[i]+=a[i-1];
		if (b[i]-b[i-1]) ans+=1;
		if (!a[i]) ans+=0.5;
	}
	printf("%.3lf",ans+1);
	return 0;
}