两个小时才会，脑子没带来？？？

NewMarchqwq · 2025-08-31 15:50:00 · 题解

看了眼别的题解做法都好妙，感觉妙妙题的妙妙方法学不会了。

先说一个常用技巧。这个题我的做法并没有用上这个，但是因为妙妙做法用了所以记录一下，等会会分别叙述两种做法的。

::::info[trick]

就是两个 Node，分别表示“min（m）和取到 min 的方法数（u）”以及“每种方法对应的权值总和（s）与方法数（c）”。它们可以很方便地定义运算，对于 min-node：

对于 sum-node：

这两种东西的定义都秉承着“加法分类，乘法分步”的加乘原理，所以代码会很自然。

::::

回到本题。首先看着这个 a 烦，先变成排列（如果两个位置值一样，想想就应该知道是位置更后的离散化完值更小），这样就可以按照值找位置了。

考虑拆贡献，什么时候 a_i 在上升子序列且有贡献？当且仅当这个子序列没有包含任何 \ge p_i 的下标，其中 p_i 满足下面两点：

这个等价转化应该很明显，那么现在就变成了下面一个问题：给定 n 个区间 [L,R]，对于每个区间有多少个只包含 [L,R] 内下标的上升子序列并且一定得包含 L（与原题的关联是这里 L=i,R=p_i-1）。这个东西我不知道能不能莫队，反正不能 polylog 应该是明显的。

考虑继续转化。容斥。把他变成算“在里面且没有贡献”的个数。也就是说必须包含 i 和 满足 j\ge p_i 且 a_j\ge a_i 的 j！这是什么！这样的 j 只有一个，就是 p_i！ 好的这是第一个关键的转化：问题变成了给定 n 个区间 [L,R]，求刚好过 a_L 和 a_R 两个位置的上升子序列的个数。怎么说呢，单纯的这个问题也是没法做的，所以还得用 p_i 的性质。

处理这个，可以用两种方法。说之前先假装我们已经处理好了其他的问题，变成了“过 a_i 和 a_{p_i} 且 a_i 是第一个，a_{p_i} 是最后一个的个数，乘 f_i。”这里 f_i 表示以 i 结尾的上升子序列个数。然后就可以思考这个问题了，先说我的。

继续瞪着 p_i 看，有第二个关键性质：对于 a_x<a_y，一定有 p_x\ge p_y——根据 p_i 的定义其实就能推出这个单调性。使用这个我们能发现我的做法最关键的地方：对于 a_j>a_i 的 j，以他开头的上升子序列，不会对 p_i 产生不应该有的贡献。 为什么呢？因为这时一定有 p_j\le p_i。而 p_j<p_i 的时候，一定是 a_j>a_{p_i} 才让 j 跳过 p_i 的，因此没问题！而对于 a_k<a_i 的 k 只需严格限定他在 BIT 上的贡献只到 a_{p_k}-1 也就行了。原因一定有 a_{p_k}\le a_{p_i}，因此不会妨碍 p_i。

综上，直接在 BIT 上给 [i,p_i-1] 部分加上自己的目前的“类 LIS 状 dp”的结果就行了。复杂度单只老哥。

::::info[code]

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll mod=1e9+7;

int n,a[200010],ia[200010],pos[200010];
ll ans=0,dp[200010],f[200010],g[200010],w[200010],c[200010];

void add(int o,ll x){for (;o<=n+1;o+=o&-o)(c[o]+=x)%=mod;}
ll ask(int o){ll x=0;for (;o;o&=o-1)x+=c[o];return x%mod;}

void solve(){
  scanf("%d",&n),ans=0;
  rep(i,1,n)scanf("%d",&a[i]),ia[i]=i;
  // 把 a 变成一个排列：相同的数，下标大的要小，方便
  sort(ia+1,ia+n+1,[&](int x,int y){
    return a[x]==a[y]?x>y:a[x]<a[y];
  });
  rep(i,1,n)a[ia[i]]=i;
  int j=n;
  rep(x,1,n){
    // 倒着寻找
    while (j&&a[j]<x)--j;
    pos[ia[x]]=j;
  }
  rep(i,0,n+5)c[i]=0;
  rep(i,1,n)f[i]=1+ask(a[i]-1),add(a[i],f[i]);
  rep(i,0,n+5)c[i]=0;
  drep(i,n,1)g[i]=1+ask(n-a[i]),add(n-a[i]+1,g[i]);
  rep(i,1,n)ans+=f[i]*g[i]%mod;
  rep(i,0,n+5)c[i]=0;
  // 正片开始
  rep(i,1,n){
    w[i]=(f[i]+ask(a[i]-1))%mod; // 计算自己答案
    add(a[i],w[i]),add(a[pos[i]],mod-w[i]); // 贡献到 a_{p_i}-1
    // cout<<i<<' '<<w[i]<<'\n';
  }
  rep(i,1,n)if (pos[i]==i)ans+=mod-w[i]; // 每个 p，只减一次，因为多个贡献已经上了
  printf("%lld\n",ans%mod);
}

int main() {
  int tt;
  scanf("%d",&tt);
  while (tt--)solve();
  return 0;
}

::::

题解区看到了另一种做法（credit: @CXY07），非常妙啊！我来按照我的理解讲一下。就是说有：如果 p_i 在 i 引出的上升子序列上，p_i 一定是 i 所引出的上升子序列的结尾，而且所有 a_k\ge a_i 的 k 所引出的上升子序列的结尾 j 一定有 j\le p_i。根据 p_i 的定义和那个单调性这是显然的，因此我们到一个 i 只需要查他到最远的地方的贡献就行了！这样我们就需要开头所说的 max-node 结构了。我们直接把所有的点丢到树状数组上，倒着做，到了 i 拿出最远的，查看这个节点 max 部分，如果不是 p_i 就丢掉，否则一定他的 cnt 就是贡献。

复杂度单只老哥。妙啊。