题意：

$N$只编号$1-N$的鼹鼠打洞，第$i$只编号为$a[i]$，编号不重复。打的洞的样子符合以$a[i]$为值，以下标为插入顺序的二叉搜索树。现在从根出发，存在左子树则先走左子树，否则往右走，每经过一个洞（结点），如果这个洞的值是奇数，就记录$1$，否则记录$0$，得到的$dfs$序列是$01$串$S$。注意是$dfs$序列不是中序遍历得到的序列，每个点最多被经过$3$次：$root->lson...lson->root->rson...rson->root$。给定一个串$T$，问$T$在$S$中出现多少次。求出$S$之后$KMP$就好惹。

关键：

某个点$a[i]$的父亲是 左边的数中 比它小的数中最大的值$L$ 或者 比它大的数的最小值$R$。 $L$和$R$都不存在，$a[i]$是根 仅$L$不存在，$a[i]$是$R$的左儿子 仅$R$不存在，$a[i]$是$L$的右儿子 都存在则$L$的右儿子和$R$的左儿子必有一个为空，$a[i]$就放在空的那个地方。 可以用$set$求$L$，$R$，但是我写会$T$;
线段树求$L$，$R$+读入挂 $2938ms/3000ms$ ，不加会$T$ 笛卡尔树$1719ms$
笛卡尔树看结点的$key$满足二叉搜索树，看结点的$value$满足堆（按具体实现分为小顶堆or大顶堆，此题小顶堆） $a[i]$为$key$，$i$为$value$，则$value$满足早点到的一定最浅，$key$满足二叉搜索树。
$S$，$T$匹配用$kmp$；注意这个二叉搜索树可能是一条链，$dfs$序列递归求可能会爆栈，用栈模拟即可√。

标程

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>

// 定义常量
const int N = 6e5 + 5;

// 全局变量声明
int t, n, x;
int fa[N], ls[N], rs[N];
int stk[N], top, stop;
char S[N * 5], T[7005];

// dfs 函数实现
void dfs(int u) {
    stk[top++] = u;
    while (top) {
        int u = stk[top - 1];
        S[stop++] = (u & 1)? '1' : '0';
        if (ls[u]) {
            stk[top++] = ls[u];
            ls[u] = 0;
        } else if (rs[u]) {
            stk[top++] = rs[u];
            rs[u] = 0;
        } else {
            top--;
        }
    }
    S[stop] = '\0';
}

// 声明数组
int nt[7000 + 5];
char b[10001];

// kmp_next 函数实现
void kmp_next() {
    nt[0] = 0;
    for (int i = 1, j = 0, m = std::strlen(T); i < m; i++) {
        while (j && T[i]!= T[j])
            j = nt[j - 1];
        if (T[i] == T[j])
            j++;
        nt[i] = j;
    }
}

// kmp 函数实现
int kmp() {
    kmp_next();
    int ans = 0, sn = std::strlen(S), tn = std::strlen(T);
    for (int i = 0, j = 0; i < sn; i++) {
        while (j && S[i]!= T[j])
            j = nt[j - 1];
        if (S[i] == T[j])
            j++;
        if (j == tn)
            ans++;
    }
    return ans;
}

// 定义结构体
struct node {
    int id, v;
    bool operator<(const node &b) const {
        return v < b.v;
    }
};

// 全局变量声明
int root;
node e[N];

// main 函数实现
int main() {
    scanf("%d", &t);
    int kase = 0;
    while (t--) {
        stop = top = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &e[i].v), e[i].id = i;
        memset(ls, 0, sizeof(ls));
        memset(rs, 0, sizeof(rs));
        memset(fa, 0, sizeof(fa));
        std::sort(e + 1, e + n + 1);
        stk[0] = 0;
        for (int i = 1; i <= n; i++) {
            while (top && e[stk[top]].id > e[i].id)
                ls[i] = stk[top], top--;
            fa[i] = stk[top];
            fa[ls[i]] = i;
            if (fa[i]) {
                rs[fa[i]] = i;
            } else {
                root = i;
            }
            stk[++top] = i;
        }
        scanf("%s", T);
        stop = top = 0;
        dfs(root);
        //  printf("%s\n",S);
        int ans = kmp();
        printf("Case #%d: %d\n", ++kase, ans);
        root = 0;
    }
    return 0;
}