[ARC212E] Drop Min 题解

FFTotoro · 2026-01-12 16:38:22 · 题解

我们需要对满足条件的 A 计数。这种“Drop Min 操作”形成的序列一眼看上去没什么很好的性质，于是先从操作入手：一个元素可以被操作（移除出 P 并加入 A），当且仅当它的左边或者右边有元素比它大。

也就是说，如果一个元素 P_i 在 A 中出现，设左边第一个比它大的元素为 P_l（如果有），右边第一个比它大的元素为 P_r（如果有），则要么 P_{l+1\ldots i-1} 在 A 中均出现得比 P_i 靠前（如果 P_l 存在），要么 P_{i+1\ldots r-1} 在 A 中均出现得比 P_i 靠前（如果 P_r 存在）。

由于这个性质类似一个“区间二选一”，所以普通的 DP 肯定是行不通的。这个时候再次审查这个结构，发现它形如“P_i 在中间，把 P_{l+1\ldots r-1} 划分成了左右两边，满足左右两边的元素都比它小”，这种划分成两边并具有特定大小关系的结构，启发我们考虑笛卡尔树上 DP。

重写一下条件：一个元素何时可以在 A 中出现，只取决于它两边的区间，即笛卡尔树上对应结点的两个儿子“管辖”的区间，是否有一边的所有元素在它之前出现——而这些元素确切的出现顺序并不重要。树的递归结构正好可以处理这样的问题：在进行 DP 时，不妨认为两棵子树各自内部元素的相对顺序已经排好了，即在当前结点处只需要做一个归并操作（左子树 / 右子树 / 自身），需要求的仅是合法的归并方案数。

建出 P 对应的大根笛卡尔树，此时 DP 的状态就很明确了：考虑一个结点 u（这里的“结点 u”指的是 P_u 对应的树上结点 (u,P_u)），两个儿子为结点 v_l,v_r，左右两边的区间大小为 L,R；设 f_u 为 u 子树内元素的合法排列数，转移必然形如 f_u=k\cdot f_{v_l}\cdot f_{v_r}，这个 k 就是在结点 u 处合法的归并方案数。由于前面提到了在 P 中可能有元素的左边 / 右边没有比它大的其他元素，故转移系数 k 的值需要分类讨论：

• 若左边和右边都没有比它大的元素，则代表它是 P 中 =N 的元素对应的结点；由于它最后留在了 P 中（并没有进入 A），所以只用把两边以任意顺序归并起来而不用考虑自身，故 k=C_{L+R}^{L}；
• 若仅有左边有比它大的元素，则所有左边的元素都必须出现得比 P_u 靠前：这个问题有个经典解法，从 L+R+1 个位置中先选定 R 个位置，把右边的 R 个元素先固定在这些位置，于是左边的元素必然会在剩下位置中的前 L 个（因为它们都要出现得比 P_u 靠前），故 k=C_{L+R+1}^{R}；
• 若仅有右边有比它大的元素，与上一种情况对称，故 k=C_{L+R+1}^{L}；
• 若两边都有元素比它大，先尝试简单地把上面两种情况对应的系数相加，发现可能会算重，会被算两遍的即为子树内所有元素（自身除外）都在 A 中比自身出现得靠前的方案数，为 C_{L+R}^{L}，扣掉就行了，故 k=C_{L+R+1}^{R}+C_{L+R+1}^{L}-C_{L+R}^{L}。

时间复杂度 O(N)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5,P=998244353;
static int fac[N+1],fi[N+1];
inline int add(int x,int y){
  int s=x+y; if(s>=P)s-=P; return s;
}
inline void self_add(int &x,int y){
  if((x+=y)>=P)x-=P;
}
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%P;
    a=1ll*a*a%P,b>>=1;
  }
  return r;
}
inline int com(int n,int m){
  return n<m?0:1ll*fac[n]*fi[m]%P*fi[n-m]%P;
} // 计算组合数
vector<pii> cartesian_tree(vector<int> p){
  int n=p.size();
  vector<pii> a(n,make_pair(-1,-1));
  stack<pii> s;
  for(int i=0;i<n;i++){
    int l=-1;
    while(!s.empty()&&s.top().second<p[i])
      l=s.top().first,s.pop();
    a[i].first=l;
    if(!s.empty())a[s.top().first].second=i;
    s.emplace(i,p[i]);
  }
  return a;
} // 建出笛卡尔树
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  for(int i=fac[0]=1;i<=N;i++)
    fac[i]=1ll*fac[i-1]*i%P;
  fi[N]=qpow(fac[N],P-2);
  for(int i=N;i;i--)
    fi[i-1]=1ll*fi[i]*i%P;
  int n; cin>>n;
  vector<int> p(n);
  for(auto &i:p)cin>>i,i--;
  auto s=cartesian_tree(p);
  auto dfs=[&](auto &&self,int u,int l,int r,bool fl,bool fr)->int{
    if(u<0)return 1;
    int kl=self(self,s[u].first,l,u-1,fl,true),
      kr=self(self,s[u].second,u+1,r,true,fr);
    int c=0;
    if(!fl&&!fr)c=com(r-l,u-l); // 两边都没有
    if(fl)self_add(c,com(r-l+1,r-u)); // 左边有
    if(fr)self_add(c,com(r-l+1,u-l)); // 右边有
    if(fl&&fr)self_add(c,P-com(r-l,u-l)); // 两边都有，要扣掉算重的
    return 1ll*kl*kr%P*c%P;
  }; // 按照文中所述的方法进行 DP
  int u=find(p.begin(),p.end(),n-1)-p.begin();
  cout<<dfs(dfs,u,0,n-1,false,false)<<endl;
  return 0;
}