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

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

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

trick

就是两个 Node，分别表示“min（

m

）和取到 min 的方法数（

u

）”以及“每种方法对应的权值总和（

s

）与方法数（

c

）”。它们可以很方便地定义运算，对于 min-node：

\begin{aligned} &(m,u)+(M,U)=\begin{cases}(m,u),&m<M\\(M,U),&m>M\\(m,u+U)&m=M&\end{cases}\\ &(m,u)\cdot(M,U)=(m+M,uU) \end{aligned}

对于 sum-node：

\begin{aligned} &(s,c)+(S,C)=(s+S,c+C)\\ &(s,c)\cdot(S,C)=(sC+Sc,cC) \end{aligned}

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

回到本题。首先看着这个

a

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

考虑拆贡献，什么时候

a_i

在上升子序列且有贡献？当且仅当这个子序列没有包含任何

\ge p_i

的下标，其中

p_i

满足下面两点：

$a_{p_i}\ge a_i$ （对， $p_i=i$ 是允许的，这时 $i$ 怎么都没有贡献）
$\forall j>p_i$ ，有 $a_j<a_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”的结果就行了。复杂度单只老哥。

code

CPP

#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 就是贡献。

复杂度单只老哥。妙啊。

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

文章操作

相关推荐

评论

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