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 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85