自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 22:36:39，当前版本为作者最后更新于2022-03-02 08:40:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

一道思维好题。

首先将题目中所给的 $l_i$ 加一，$r_i$ 减一，发现这就是笛卡尔树的“影响区间”，再观察一下部分分，发现 Subtask 3,4 中说的是“存在一个排列”，但如果是仅仅存在一个排列这挡部分分意义就不大。我们于是大胆猜测对于一个重排后的 $l_i,r_i$ 数组，能确定的笛卡尔树形态是唯一的。

思考 Subtask 3,4 的做法。对 $l_i,r_i$ 建笛卡尔树后相当于要往树上填一些数字 $S=\{1,2,3,\dots,n\}$ ，使其满足小根堆性质。对于当前的备选集合 $S$ ，为了满足小根堆性质，我们必须把 $S$ 中最小的数填到当前的根，然后再把 $S$ 分成两个集合 $S_1,S_2$ 填到左右儿子上。

具体地，设 $f_u$ 表示大小为 $size_u$ 的备选集合 $S$ 填到节点 $u$ 的方案数，那么可以推出：

$$f_u=f_{lson_u}\times f_{rson_u} \times {size_u-1\choose size_{lson_u}} $$

$f_{root}$ 即为答案，这部分子任务的代码：

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int read(){
	//……
}
const int _=1000003;
const int P=998244353;
int inv[_],fac[_],fiv[_];
int n;
int L[_],R[_];
vector<int> g[_];
int f(int l,int r){
	g[l].pop_back();
	if(l+1>=r-1) return 1;
	int p=g[l].empty()?l+1:g[l].back();
	int lc=f(l,p),rc=f(p,r);
	return 1ll*lc*rc%P*fiv[p-l-1]%P*fiv[r-p-1]%P*fac[r-l-2]%P;
}
void solve(){
	for(int i=0;i<n;++i) g[i].clear();
	for(int i=1;i<=n;++i) g[L[i]].emplace_back(R[i]);
	for(int i=0;i<n;++i) sort(g[i].begin(),g[i].end());
	printf("%d\n",f(0,n+1));
}
int main(){
	n=read();fac[0]=fiv[0]=inv[1]=1;
	for(int i=1;i<=n;++i) L[i]=read();
	for(int i=1;i<=n;++i) R[i]=read();
	for(int i=2;i<=n;++i) inv[i]=1ll*inv[P%i]*(P-P/i)%P;
	for(int i=1;i<=n;++i) fac[i]=1ll*i*fac[i-1]%P;
	for(int i=1;i<=n;++i) fiv[i]=1ll*inv[i]*fiv[i-1]%P;
	solve();
	return 0;
}

有了 $55$ 分，证明结论正确。

那么对于一个重排后的 $l_i,r_i$ 数组，一定存在一种方式构造出唯一一种笛卡尔树。

再次对题目性质进行观察，抓住重排不变量，也就是每个边界的出现次数，考虑对于笛卡尔树形态的影响。

对于上图的笛卡尔树，2 作为右边界出现两次，4 作为左边界出现两次。

一个数 $a_i$ 开始作为右边界出现的时候，就是 $a_{i+1}$ 变成了一个区间的最小值，将序列分割成了 $[l_{i+1},i]$ 和 $[i+2,r_{i+1}]$。$a_i$ 会一直成为右边界直到到达他自己作为一个区间最小值的节点。那么发现笛卡尔树上的深度差 $deep_{i}-deep_{i+1}$ 恰好就是 $i$ 作为右边界的出现次数。左边界同理，只不过是 $deep_{i}-deep_{i-1}$。

由于相邻两数要么 $deep_{i}>deep_{i+1}$ 要么 $deep_{i}<deep_{i+1}$，那么我们就可以用重排后的 $l_i,r_i$ 得到整个 $deep$ 数组的相对大小关系，强制 $deep_1=0$ 后求出 $deep$ 数组直接单调栈建笛卡尔树，再跑上述树形 $DP$ ，这道题也就做完了。

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	//……
}
const int _=1000003;
const int P=998244353;
int inv[_],fac[_],fiv[_];
int n;
int cL[_],cR[_],a[_],sz[_];
int lc[_],rc[_],stk[_],tp;
int solve(int u){
	if(!u) return 1;
	int lo=solve(lc[u]),ro=solve(rc[u]);
	sz[u]=sz[lc[u]]+sz[rc[u]]+1;
	return 1ll*lo*ro%P*fac[sz[lc[u]]+sz[rc[u]]]%P*fiv[sz[lc[u]]]%P*fiv[sz[rc[u]]]%P;
}
int main(){
	n=read();fac[0]=fiv[0]=inv[1]=1;
	for(int i=1;i<=n;++i) ++cL[read()+1];
	for(int i=1;i<=n;++i) ++cR[read()-1];
	for(int i=2;i<=n;++i) inv[i]=1ll*inv[P%i]*(P-P/i)%P;
	for(int i=1;i<=n;++i) fac[i]=1ll*i*fac[i-1]%P;
	for(int i=1;i<=n;++i) fiv[i]=1ll*inv[i]*fiv[i-1]%P;
	a[1]=0;
	for(int i=2;i<=n;++i){
		if(cL[i]) a[i]=a[i-1]+cL[i];
		if(cR[i-1]) a[i]=a[i-1]-cR[i-1];
	}
	for(int i=1;i<=n;++i){
		while(tp>1&&a[i]<a[stk[tp-1]]) rc[stk[tp-1]]=stk[tp],--tp;
		if(a[i]<a[stk[tp]]) lc[i]=stk[tp],stk[tp]=i;
		else stk[++tp]=i;
	}
	while(tp>1) rc[stk[tp-1]]=stk[tp],--tp;
	printf("%d\n",solve(stk[tp]));
	return 0;
}

听说这道题有只用 $l_i$ 数组的做法，希望有大佬可以发题解指教。