[EZEC-11] Unmemorable 题解
yyyyxh
·
·
题解
一道思维好题。
首先将题目中所给的 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}}
```cpp
#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$ ，这道题也就做完了。
```cpp
#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$ 数组的做法，希望有大佬可以发题解指教。