Codeforces1913 D. Array Collapse（笛卡尔树+树上dp）

题意：

解法：

容易想到区间dp
令dp[l][r]表示区间l,r的方案数

设[l,r]内最小的数下标为x:
如果x不删除,则d[l][r]+=d[l][x-1]*d[x+1][r].
如果x删除,考虑x被哪边删除,
1.如果l!=1,说明x可以被左边的某个数删除,
则方案数为区间右边的方案数,d[l][r]+=d[x+1][r];
2.如果r!=n,说明x可以被右边的某个数删除,
则方案数为区间左边的方案数,d[l][r]+=d[l][x-1];
3.如果l!=1并且r!=n,说明左右两边都可以删除x,
此时[l,r]整个区间被删除的方案数重复计算了,
因此d[l][r]-=1.

复杂度O(n^2),这题n<=3e5,需要优化.

可以建立笛卡尔树，
笛卡尔树每棵子树的根节点对应一段区间[l,r]的最小值x.
左子树表示区间[l,x-1],右子树表示区间[x+1,r]
我们在树上dp即可.
复杂度O(n)

Code：

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define PI pair<int, int>
const int maxm=3e5+5;
const int mod=998244353;

int n;
int a[maxm];
int lc[maxm],rc[maxm]; 
int stk[maxm];
int d[maxm];
int build(){
  for(int i=1;i<=n;i++){
    lc[i]=rc[i]=0;
  }
  int head=0;
  for(int i=1;i<=n;i++){
    int tp=head;
    while(tp&&a[stk[tp]]>a[i])tp--;
    if(tp)rc[stk[tp]]=i;
    if(tp+1<=head)lc[i]=stk[tp+1];
    head=tp;
    stk[++head]=i;
  }
  return stk[1];
}
void dfs(int x,int l,int r){
  if(!x)return ;
  d[x]=0;
  dfs(lc[x],l,x-1);
  dfs(rc[x],x+1,r);
  // x不删除
  int sl=(d[lc[x]])%mod;
  int sr=(d[rc[x]])%mod;
  d[x]=(d[x]+sl*sr)%mod;
  // x被左边的数删除
  // l!=1说明左边有更小的数
  if(l!=1){
    d[x]=(d[x]+d[rc[x]])%mod;
  }
  // x被右边的数删除
  // r!=n说明右边有更小的数
  if(r!=n){
    d[x]=(d[x]+d[lc[x]])%mod;
  }
  // 当x可以同时被左边/右边删除时
  // 当[l,r]整个区间被删除的方案会计算重复
  // 所以这里要减1
  if(l!=1&&r!=n){
    d[x]=(d[x]-1)%mod;
  }
}
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  int rt=build();
  d[0]=1;
  dfs(rt,1,n); 
  int ans=d[rt];
  ans=(ans%mod+mod)%mod;
  cout<<ans<<endl;
}
signed main() {
#define MULTI_CASE
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
  int T;
  cin >> T;
  while (T--)
#endif
    solve();
  return 0;
}

---