专栏文章

In-order 题解

yyh2022mayu
P13804题解参与者 10已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
14 条
当前快照
1 份
快照标识符
@min8o1mn
此快照首次捕获于
2025/12/01 22:22
3 个月前
此快照最后确认于
2025/12/01 22:22
3 个月前
查看原文

/update 2025/11/18 美化了一下latex

题目链接

前言

我太蒻了，模拟赛场上没想出来，赛后看的同机房大手子郑哥（OtterZ）的题解才做出来的，所以没有部分分的算法，如果希望体验部分分，请看郑哥的题解（因该一共就两篇吧）。

solution

首先，我们先不考虑中序遍历对于答案的影响，看只有前序和后序对答案有什么约数。
通过前序后序排列的性质，不难发现，我们可以得出每一个点有多少个儿子，还可以知道儿子具体是谁。具体的，我们可以这样做：设当前子树根节点为 uu ，且我们得到了 uu 子树前序遍历在整体前序遍历中处于 [la,ra][la,ra] 的位置，uu 子树后序遍历在整体后序遍历中处于 [lb,rb][lb,rb] 的位置，那么 ala+1a_{la+1}，brb−1b_{rb-1} 就是 uu 的两个儿子，若 ala+1a_{la+1}，brb−1b_{rb-1} 相同，那么 uu 只有一个儿子。对于两个儿子，我们分别找到他们在前序遍历和后序遍历中的位置从而计算出对应的区间，递归下去。对于只有一个儿子，我们直接把 uu 从区间中扣掉然后递归下去。
现在我们建出了一棵树，使得所有答案方案如果不考虑左右儿子的话都与之同构。
那么，现在的唯一变数就是那些只有一个儿子的点到底有左儿子还是有右儿子。我们称这些点为摇摆点。设总的摇摆点个数为 cntcnt。
现在再来考虑中序遍历的影响，分三种情况讨论。
下面我们称中序遍历中不为 00 的点为关键点。

没有关键点

那么没有任何影响，我们快乐的输出 2cnt2^{cnt} 即可。

一个关键点

我们考虑所有摇摆点的选择对于关键点的影响。发现如果摇摆点不在关键点到根的路径上，那么没有影响。如果在到根的路径上，那么每将这样的一个摇摆点从左儿子改为右儿子都会使得原本在关键点之后的摇摆点变到关键点之前，从而使得关键点中序遍历的位置向后挪一位。
那么我们就先钦定所有摇摆点选左儿子，然后计算此时关键点的中序遍历位置，然后在挑出当前中序遍历位置和实际中序遍历位置差值个摇摆点从左儿子变为右儿子，剩下不在路径上的摇摆点的左右儿子任选。这是一个组合数就可以解决的问题。
当然，有一个细节，如果关键点本身就是一个摇摆点，那么我们要分情况讨论关键点选左儿子还是右儿子（就是中序遍历位置算不算上左儿子子树大小）。

多个关键点

由于题目给的是一段完整的区间，所以两个相邻的关键点一定在中序遍历上也相邻。
这一点很重要，这样我们就能唯一确定两个相邻关键点上摇摆点的选择。我们考虑如何将这些摇摆点变成非摇摆点从而计算答案。
由于每个点只用遍历到一次即可，你当然可以选择计算相邻的 lca 然后用经典的并查集维护来暴力跳。其实还有一个更加暴力的做法，首先有两个结论：
1.1. 中序遍历上相邻的两个点其中一个是另一个的祖先，这个很好理解，如果不是的话那他们的 lca 一定夹在两个点之间。
2.2. 所有中序遍历相邻的点的树上距离之和为 2n2n，这是因为一个子树的中序遍历也是连续的，所以从子树连向外界的边只会在进入和出子树的时候被访问到。有了以上两个结论，我们就可以开一个 visvis 数组表示每个点是否已经从摇摆点变为非摇摆点，然后暴力从那个为子孙节点的关键点向上跳，直到跳到为祖先的关键点，当前点没改的时候我们就把他改掉（修改就是将 cntcnt-- 并且将这个点的对应儿子赋值）。
这里有一个细节和第二种情况不同，就是所有关键点就算是摇摆点最终的选择还是固定的。
修改完之后剩下的操作就类似第二种了，我们在求一边中序遍历，对于那些没改的摇摆点，我们还是钦定选左儿子，然后取出所有关键点的 lca，lca 到根上的每一个摇摆点从左儿子变为选右儿子都将使得所有关键点的位置后移，所以我们类似第二种操作做就可以了。
这里有一个问题，那就是在 lca 子树里但不在相邻关键点路径上的摇摆点的选择会不会影响答案呢，仔细想一想发现答案是不会的，因为只要不在路径上你无论如何选都只是影响子树内部的排序。
时间复杂度 O(n)O(n)（不用真的求 lca，直接找深度最小的关键点就是了）。
具体的细节见代码注释。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll md = 999999937;
inline int read(){
	char c = getchar();
	int ans = 0, cnt = 1;
	while(c < '0' || c > '9'){
		if(c == '-') cnt = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		ans *= 10;
		ans += (c - '0');
		c = getchar();
	}
	return ans * cnt;
}
ll ksm(ll a, ll b, ll md){
	ll ans = 1;
	a %= md;
	while(b){
		if(b % 2) ans = ans * a % md;
		a = a * a % md;
		b /= 2;
	}
	return ans;
}
ll jc[1000005], ny[1000005];
ll C(int a, int b, ll md){
	if(b > a || a < 0 || b < 0) return 0;
	return jc[a] * ny[b] % md * ny[a - b] % md;
}
ll A(int a, int b, ll md){
	if(b > a || a < 0 || b < 0) return 0;
	return jc[a] * ny[a - b] % md;
}
void initAC(ll md){
	jc[0] = ny[0] = 1;
	for(int i = 1; i <= 1000000; i++) jc[i] = jc[i - 1] * i % md, ny[i] = ksm(jc[i], md - 2, md);
}
int n;
int a[1000005], b[1000005], c[1000005];
int ida[1000005], idb[1000005];
int is[1000005], rnk[1000005], f[1000005], cnt, vis[1000005], d[1000005], tot, sz[1000005], ls[1000005], rs[1000005];
int l, r;
void bld(int la, int ra, int lb, int rb, int dt){
	int u = a[la];
	d[u] = dt;
	sz[u] = 1;
	if(la == ra){
		rnk[u] = ++tot;
		return ;
	}
	ls[u] = a[la + 1], rs[u] = b[rb - 1];
	if(ls[u] != rs[u]){
		f[ls[u]] = f[rs[u]] = u;
		bld(la + 1, ida[rs[u]] - 1, lb, idb[ls[u]], dt + 1);
		rnk[u] = ++tot;
		bld(ida[rs[u]], ra, idb[ls[u]] + 1, rb - 1, dt + 1);
		sz[u] += sz[ls[u]] + sz[rs[u]];
	}
	else{
		rs[u] = 0;
		f[ls[u]] = u;
		bld(la + 1, ra, lb, rb - 1, dt + 1);
		rnk[u] = ++tot;
		is[u] = 1;
		cnt++;
		sz[u] += sz[ls[u]];
	}
}
void dfs(int u){
	if(!u) return ;
	dfs(ls[u]);
	rnk[u] = ++tot;
	dfs(rs[u]);
}
signed main(){
	srand(time(0));
	initAC(md);
	cin >> n;
	for(int i = 1; i <= n; i++) a[i] = read(), ida[a[i]] = i;
	for(int i = 1; i <= n; i++) b[i] = read(), idb[b[i]] = i;
	bld(1, n, 1, n, 1);
	for(int i = 1; i <= n; i++){
		c[i] = read();
		if(c[i]){
			if(!l) l = i;
			r = i;
		}
	}
	int ans;
	if(!l){
		cout << ksm(2, cnt, md);
		return 0;
	}
	if(l == r){
		int u = f[c[l]], sum = 0;
		while(u){
			if(is[u]) cnt--, sum++;
			u = f[u];
		}
		if(is[c[l]]) cnt--;
		cout << ksm(2, cnt, md) * (C(sum, l - rnk[c[l]], md) + (is[c[l]]) * C(sum, l - rnk[c[l]] + sz[ls[c[l]]], md)) % md;
		return 0;
	}
	int lca = 0;
	for(int i = l; i <= r; i++){
		if(!lca) lca = c[i];
		else if(d[c[i]] < d[lca]) lca = c[i];
		if(i < r){
			int u = c[i], v = c[i + 1];
			if(d[u] < d[v]){
				if(!vis[v]){
					vis[v] = 1;
					if(is[v]) swap(ls[v], rs[v]), cnt--;
				}
				v = f[v];
				while(v != u){
					if(!vis[v]){
						vis[v] = 1;
						if(is[v]) cnt--;
					}
					v = f[v];
				}
				if(!vis[u]){
					vis[u] = 1;
					if(is[u]) swap(ls[u], rs[u]), cnt--;
				}
			}
			else{
				if(!vis[u]){
					vis[u] = 1;
					if(is[u]) cnt--;
				}
				u = f[u];
				while(v != u){
					if(!vis[u]){
						vis[u] = 1;
						if(is[u]) cnt--, swap(ls[u], rs[u]);
					}
					u = f[u];
				}
				if(!vis[v]){
					vis[v] = 1;
					if(is[v]) cnt--;
				}
			}
		}
	}
	tot = 0;
	dfs(a[1]);//血的教训，这里不是1
	int u = f[lca], sum = 0;
	while(u){
		if(is[u]) cnt--, sum++;
		u = f[u];
	}
	cout << ksm(2, cnt, md) * C(sum, l - rnk[c[l]], md) % md;
	return 0;
}

彩蛋

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...