有些人还是啥都不会。
看到题目应该能想到这是笛卡尔树的性质，因为每一对 \((l,r)\) 都满足最左端最大值位置相同，所以说明在笛卡尔树上，每一对点的 lca 相同，说明 \(a\) 和 \(b\) 序列的笛卡尔树相同。
我们以下标为键，\(a_i\) 为值建立大根笛卡尔树，现在题目就转换成在这个树上填值满足笛卡尔树的形态不变。
因为计数，考虑动态规划，设 \(dp_{u,j}\) 表示当前点为 \(u\)，填写了 \(j\) 的方案数，分三类讨论即可。
- 如果没有儿子，\(dp_{u,j}=1\)。
- 如果只有一个儿子，如果是左儿子，那左儿子只能填 \([1,j-1]\)，因为根据键的性质，左儿子键值小于 \(u\)，如果填了大于 \(j-1\) 的数的话，就不满足左端最大值在 \(u\) 的限制条件了，而是在左儿子。如果是只有右儿子的话，那右儿子填 \([1,j]\) 均可。
- 如果有两个儿子，根据上文，左儿子可以填 \([1,j-1]\)，右儿子可以填 \([1,j]\)，加法原理即可。
具体转移方程见代码。
这个转移显然是可以 \(O(m)\) 搞出来的，所以总时间就是 \(O(\sum n \times m)\)。
注意要用 vector 来开数组。
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
const int mod=1e9+7;
#define int long long
struct node{
int l,r;
}dis[N];
struct edge{
int v,id;
};
struct node1{
int k,w;
};
int t,n,m,a[N];
vector<long long> dp[N];
vector<edge> g[N];
stack<node1> sta;
void Clear(){
for(int i=1;i<=n;i++) g[i].clear(),dp[i].clear(),dis[i].l=dis[i].r=0;
}
void DP(int u){
dp[u].push_back(0);
if(g[u].size()==0) for(int i=1;i<=m;i++) dp[u].push_back(1);
else if(g[u].size()==1){
DP(g[u][0].v);
int sum=0;
if(g[u][0].id==1) for(int i=1;i<=m;i++) dp[u].push_back(sum),sum+=dp[g[u][0].v][i],sum%=mod;
else for(int i=1;i<=m;i++) sum+=dp[g[u][0].v][i],dp[u].push_back(sum),sum%=mod;
}
else{
DP(g[u][0].v),DP(g[u][1].v);
int sum1=0,sum2=0;
for(int i=1;i<=m;i++) sum2+=dp[g[u][1].v][i],sum2%=mod,dp[u].push_back((sum1%mod*sum2%mod)%mod),sum1+=dp[g[u][0].v][i],sum1%=mod;
}
}
void Slove(){
for(int i=1;i<=n;i++){
int lst=0;
while(!sta.empty()&&a[i]>sta.top().w) lst=sta.top().k,sta.pop();
if(sta.empty()) dis[i].l=lst;
else{
int now=sta.top().k;
dis[i].l=dis[now].r;dis[now].r=i;
}
sta.push({i,a[i]});
}
for(int i=1;i<=n;i++){
if(dis[i].l!=0) g[i].push_back({dis[i].l,1});
if(dis[i].r!=0) g[i].push_back({dis[i].r,0});
// cout<<i<<" "<<dis[i].l<<" "<<dis[i].r<<endl;
}
int lst1=0;
while(!sta.empty()) lst1=sta.top().k,sta.pop();
DP(lst1);
// cout<<lst1<<" ";
long long ans=0;
for(int i=1;i<=m;i++) ans+=dp[lst1][i],ans%=mod;
cout<<ans<<endl;
Clear();
// cout<<dp[2][2]<<endl;
}
signed main(){
cin>>t;
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Slove();
}
}
/* chong xin an pai zhi
dp[u][j] = dp[v1][1-->j-1]*dp[v2][1-->j]
*/
/*
4
4 2
2 2 2 2
*/