https://oi-wiki.org/ds/cartesian-tree/

概念

给一个长度为n的数组a[i]。构造一棵小根笛卡尔树。这棵笛卡尔树会满足：
1.是一棵二叉树
2.中序遍历其下标的结果是1~n。
3.每个节点a[i]满足小根堆的性质。

严谨的定义是：给出一些键值对$(k,w)$。笛卡尔树要求 $k $满足二叉搜索树的性质，而 $w$ 满足堆的性质。如果笛卡尔树的 $k,w$ 键值确定，且 $k $互不相同，$w $也互不相同，那么这棵笛卡尔树的结构是唯一的。

ps.以下笛卡尔树都指的是小根笛卡尔树

构造

O(nlogn)构造

从定义出发，根节点就是数组下标[1~n]中的最小值(i,a[i])，左子节点就是[1~i-1]的最小值。右子节点就是[i+1~n]的最小值。递归构造即可，查询最小值使用st表。时空复杂度都是O(nlogn)

O(n)构造

只要我们能知道如何往笛卡尔树中插入一个元素，其实就知道怎么构造出一棵笛卡尔树。
我们按k从小到大插入，那么新插入的元素（键值对），在笛卡尔树中的位置一定是其最右链！

我们在最右链中找到从根节点往下，最后一个w小于等于新键值对的w的节点。根据二叉搜搜素和性质和小根堆性质，这个节点应是新键值对的父节点。其右子节点应是新键值对的左子节点。

所以只需要维护最右链，并且能快速找到最后一个w小于等于新键值对的节点。很明显使用单调栈即可。
这里给出一个笛卡尔树模板：

constexpr int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node {
  int idx, val, par, ch[2];//在数组的下标、值、父节点、左右子节点

  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];

int cartesian_build(int n) {  // 建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}

// tree[0].init(0, 0, 0);
// for (int i = 1; i <= n; i++) {
//     cin >> hi;
//     tree[i].init(i, hi, 0);
// }
// root = cartesian_build(n);

例题 [COCI2008-2009#4] PERIODNI

ps.以下用h表示层数，即h[i]表示第i个位置的层数。

简单观察，题目例子中的两个a之所以是合法的，就是因为其中间存在更小的层数。所以假设我们对某个区间计数，答案既与该区间的“较小值”相关，也与最小值左右两边的性质相关。而笛卡尔树似乎能串联这两个性质。
此外，多边形+dp，考虑笛卡尔树似乎是个很常见的trick。。。但是我还对此没有什么体悟。

考虑构造一个笛卡尔树。使用一个常用的dp表示$dp[u][k]=以u节点为根的子树中，放置k个数字的方案数$

以该状态表示考虑状态转移方程，似乎无法成功，因为你如果在所有层数中随意摆放，你几乎无法利用小根堆的性质。我们采用笛卡尔树就是因为题目中‘a’这个例子：左右两边的层数都比当前根节点层数大，在根节点的层数之上的同一层，左右两边摆放数字是合法的。

这引发我们发现，在根节点层数之上，左右两边摆放方案是互相独立的，因此在状态表示中我们需要限制摆放的层数。

那么如何限制层数呢。再回到刚刚发现的结论，再左右儿子摆放方案独立的性质一直保持到根节点层数+1。这提示我们状态表示中限制层数可以是其父节点层数+1以上。实际上就该是父节点层数+1，因为这会让状态集合的另一部分图形是一个矩形，容易计算。具体来说，我们的状态表示是：
$$dp[u][k]:在以u为根的子树中，在层数大于h[father[u]]中摆放k个数字的方案数$$
其答案一方面来自u的左右儿子中，在h[u]以上摆放的方案。另一方面来自在h[fa[u]到h[u]中摆放的方案。其中，由于小根堆性质，该子树中所有位置的层数都大于等于h[fa[u]]，所以第二部分的图形是一个矩形，不会有比这更容易求的答案的图形形状了！

$$考虑状态转移。第一部分，如果只在h[u]上方摆放：dp[u][k] += \sum_{j=0}^k dp[lson][j] * dp[rson][k-j]$$

在得到第一部分答案的基础上，第二部分。如果允许在下方矩形处也摆放数字。这个矩形的高度H是$h[u] - h[fa[u]]$，宽度W是子树大小。H行选j行、W列选j列，选出的j列对应到j行是一个全排列。因此在下方摆放j个数字的方案数是：
$$C(H,j)*C(W,j)*j\ !$$
注意状态转移时，上方摆放情况会影响下方，并不是互相独立的了。上方摆放过的列，下方就不能摆放了，所以真实列数是$W-(上方摆放数的数量)$。

综上第二部分的方程是：
$$dp[u][k] += \sum_{j=1}^k dp[u][k-j] * C(H,j)*C(W-(k-j),j)*j\ !$$

实现代码：注意由于用到了形如$dp[u][k-j]$，状态转移时j从大到小遍历。
注意由于提前设置了dp[u][0] = 1，状态转移时不能重复计算两部分都摆放0个的情况。

#include<bits/stdc++.h>
#define endl '\n'
#define int ll
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

//dp：i子树内，在大于a[father]的位置放置k个数的方案数
//ans：根节点的a[father]设为0 dp[root][k];
const int N = 510;
const ll mod = 1e9+7;

ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res= res*a%mod;
        b>>=1;
        a= a*a%mod;
    }
    return res%mod;
}

ll fact[1000010],ifact[1000010];
void init(){
    fact[0] = ifact[0]=1;
    for(int i=1;i<=1000000;i++){
        fact[i] = fact[i-1]*i%mod;
        ifact[i] = ifact[i-1]*qmi(i,mod-2)%mod;
    }
}
ll C(ll n,ll m){
    if(n<m) return 0;
    return fact[n]*ifact[m]%mod * ifact[n-m]%mod;
}
ll A(ll n,ll m){
    if(m>n) return 0ll;
    return fact[n]*ifact[n-m]%mod;
}


int n,k;
vector<int> w;
struct node {
  int idx, val, par, ch[2];//在数组的下标、值、父节点、左右子节点
  int siz = 1;  
  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];

int cartesian_build(int n) {  // 建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}
vector<vector<int>> dp;
void dfs(int u,int fa){
    if(!u) return;  
    int val = w[u] - w[fa];
    dp[u][0] = 1;
    //1.通过子节点更新  2.在该层放置，高度是[a[father]+1,a[i]]，宽度区间是：子树大小
    for(int i=0;i<2;i++){
        int son = tree[u].ch[i];
        if(son==0) continue;
        dfs(son,u);
        tree[u].siz += tree[son].siz;
        for(int j=k;j>=0;j--)
            for(int v=1;v<=j;v++)//注意从1开始，因为我们已经提前设置了dp[u][0] = 1，否则这里会重复计算一次;
                dp[u][j] = (dp[u][j] + dp[son][v] * dp[u][j-v]%mod)%mod;
    }
    for(int i  = k;i>=0;i--){
        for(int j = 1;j<=i;j++){//注意从1开始，因为我们已经提前设置了dp[u][0] = 1;
            dp[u][i] = (dp[u][i] + dp[u][i-j]*C(val,j)%mod *C(tree[u].siz-i+j,j)%mod *fact[j]%mod)%mod;
        }
    }
}

void solve(){
    init();
    cin>>n>>k;tree[0].init(0, 0, 0);
    w = vector<int>(n+1);
    for(int i=1;i<=n;i++){
        cin>>w[i];
        tree[i].init(i, w[i], 0);
    }
    int root = cartesian_build(n);
    dp = vector<vector<int>>(n+1,vector<int>(k+1,0));
    dfs(root,0);
    cout<<dp[root][k]<<endl;
}

signed main(){      
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}