大意: 给定$n$元素序列$a$, 依次插入二叉搜索树, 求出$dfs$序列, 对序列每个元素模$2$得到一个长为$2n-1$的$01$序列$s1$. 再给定$01$序列$s2$, 求$s2$在$s1$中的出现次数.
二叉搜索树的一个节点$x$, 右儿子是满足$a[y]>a[x],y>x$的最小$y$, 左儿子是满足$a[y]<a[x],y>x$的最小$y$.
所以按照$a$排序后, 编号的笛卡尔树就是二叉搜索树.
大意: 给定$n$元素序列$a$, 依次插入二叉搜索树, 求出$dfs$序列, 对序列每个元素模$2$得到一个长为$2n-1$的$01$序列$s1$. 再给定$01$序列$s2$, 求$s2$在$s1$中的出现次数.
二叉搜索树的一个节点$x$, 右儿子是满足$a[y]>a[x],y>x$的最小$y$, 左儿子是满足$a[y]<a[x],y>x$的最小$y$.
所以按照$a$排序后, 编号的笛卡尔树就是二叉搜索树.