Description
太抽象了
给定一个二叉堆（小根）节点权值的中序遍历，求可能的前序遍历个数。\(n \le 10^6\)。
Solution
由中序遍历的性质，一定是在区间 \([l,r]\) 内选一个点 \(p\) 令 \(p\) 为根，然后再分别递归处理 \([l,p-1]\) 和 \([p+1,r]\)。
由题意有 \(h_p=\min_{i=l}^{r}{h_i}\)。令 \(P\) 为满足条件 \(p\) 的集合，区间 \([l,r]\) 的答案 \(res_{l,r}=\sum_{p \in P}{res_{l,p-1}\times res_{p+1,r}}\)。边界条件 \(res_{l,l}=res{l,l-1}=1\)。如果序列中元素均相同就炸了，复杂度 \(O(n^2)\)。
\([l,r]\) 间的所有最小值一定集中在二叉堆的“上方”，把这些结点抠出来排成二叉树，其他的区间作为子树接在下方。设区间内有 \(k\) 个最小值，则有 \(k+1\) 个多余的子树（其中有部分子树为空），而二叉树上有 \(2k-(k-1)=k+1\) 个子节点，一一对应。因此只需计算这些区间的答案之积，再把答案乘上大小为 \(k\) 二叉树的形态数。这是经典的卡特兰数 \(Cat_k\)。
最小值遍历区间会炸，用 st 表处理区间最小值最靠左的位置，预处理出下一个同色位置直接跳即可。这样每个点只会被遍历 \(O(1)\) 次，复杂度瓶颈在 st 表预处理 \(O(n \log n)\)。
Code
#include<bits/stdc++.h>
#define inf 1e9
#define ll long long
using namespace std;
const int N=1e6+20,mod=1e9+7;
int n,h[N],nxt[N],pos[N];
int st[21][N],lg[N];
int fac[N<<1],inv[N]; //注意一下空间上的细节int get(int x,int y){return (h[x]<h[y]||(h[x]==h[y]&&x<y))?x:y;}
int gtmin(int l,int r)
{int x=lg[r-l+1];return get(st[x][l],st[x][r-(1<<x)+1]);
}
int Cat(int x){return 1ll*fac[x<<1]*inv[x]%mod*inv[x+1]%mod;}
int solve(int l,int r)
{if(l>=r)return 1;int p=gtmin(l,r),tot=1;int res=solve(l,p-1);while(nxt[p]<=r)tot++,res=1ll*res*solve(p+1,nxt[p]-1)%mod,p=nxt[p];res=1ll*res*solve(p+1,r)%mod;return 1ll*res*Cat(tot)%mod;
}void init()
{inv[1]=1;for(int i=2;i<=1e6+10;i++){lg[i]=lg[i>>1]+1;inv[i]=(mod-1ll*inv[mod%i]*(mod/i)%mod);}fac[0]=1;for(int i=1;i<=2e6;i++)fac[i]=1ll*fac[i-1]*i%mod;inv[0]=1;for(int i=1;i<=1e6+10;i++)inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init();cin>>n;for(int i=1;i<=n;i++)cin>>h[i];for(int i=n;i>=1;i--){st[0][i]=i;nxt[i]=n+1;if(pos[h[i]])nxt[i]=pos[h[i]];pos[h[i]]=i;}for(int i=1;i<=lg[n];i++)for(int j=1;j+(1<<i)-1<=n;j++)st[i][j]=get(st[i-1][j],st[i-1][j+(1<<(i-1))]);cout<<solve(1,n)<<"\n";return 0;
}