J. Counting Trees (树，卡特兰数)
题目
https://codeforces.com/gym/102501/problem/J
大意就是，规定一棵二叉树，每个节点的值都大于等于其父节点的值。给出一个中序遍历值序列，问有多少棵这样的树满足其中序遍历是这个。
节点数范围 1e6，节点值范围 1e6。
思路
-
中序遍历，满足一棵子树映射到序列中一段区间。
-
对于一个区间，若它代表一个子树，那么该子树的根就是区间内最小的值。
-
若区间内有多个最小的值，那这些位置应该组成一个包含子树根的连通块，这些点分割出来的区间，分别代表下面的一棵子树。连通块有多种可能，不过一旦确定出这个连通块形态（即这几个点组成的树的形态），那么分割出的几棵子树位置就确定了。
-
也就是说，变成了一个递归问题。对于子树
[L, R]，取出其中最小的值，假设是x[1], x[2], ..., x[k]，那么答案就是递归求出分出来的 k+1 个区间的答案之积，再乘上满足中序遍历是 1, 2, …, k 的二叉树个数。 -
乘上的这个数，其实就是卡特兰数
Cat[k]。考虑一棵二叉树的中序遍历其实对应出一种出入栈序列。 -
卡特兰数可以看这个博客 https://blog.csdn.net/chenlong_cxy/article/details/113613203
代码
#include <bits/stdc++.h>
using namespace std;
#define Ha 1000000007
#define MAXN 1000005
long long Cat[MAXN];
int n;
int a[MAXN];
int ST[MAXN][25];
vector<int> pos[MAXN];
long long ksm(long long x, int k)
{
long long ret=1;
for (; k; k>>=1, x=x*x%Ha)
if (k&1) ret = ret*x%Ha;
return ret;
}
int getMin(int L, int R)
{
int k = R-L+1;
int ret=a[L];
int cur = L;
for (int i=0; i<=20; i++) {
if (k&(1<<i)) {
ret = min(ret, ST[cur][i]);
cur+=(1<<i);
}
}
return ret;
}
long long dfs(int L, int R)
{
if (L>=R) return 1;
int mn = getMin(L, R);
long long ret=1, cnt=0;
int lst=L, cur;
auto pl = lower_bound(pos[mn].begin(), pos[mn].end(), L);
while (pl!=pos[mn].end() && *pl<=R) {
cnt++;
cur = *pl;
ret = ret * dfs(lst, cur-1) %Ha;
lst = cur+1;
pl++;
}
ret = ret * dfs(lst, R) %Ha;
ret = ret * Cat[cnt] %Ha;
return ret;
}
void solve()
{
scanf("%d", &n);
Cat[0] = 1;
for (int i=0; i<n; i++) Cat[i+1] = Cat[i]*(i*4+2)%Ha *ksm(i+2, Ha-2) %Ha;
for (int i=1; i<=n; i++) {
scanf("%d", &a[i]);
ST[i][0] = a[i];
pos[a[i]].push_back(i);
}
for (int j=1,jj=1; j<=20; j++,jj<<=1)
for (int i=1; i+jj<=n; i++)
ST[i][j] = min(ST[i][j-1], ST[i+jj][j-1]);
long long ans = dfs(1, n);
ans = (ans+Ha)%Ha;
printf("%lld\n", ans);
}
int main()
{
solve();
return 0;
}