CF1621G Weighted Increasing Subsequences（离散化+树状数组优化dp+栈维护后缀最大值+计数）_维护最大后缀高度

problem

luogu-link

solution

显然单独考虑每个 $i$ 的贡献，即被多少个合法上升子序列包含。

令 x = max ⁡ { j   ∣   j > i ∧ a j > a i } x=\max\{j\ |\ j>i\wedge a_j>a_i\} x=max{j ∣ j>i∧aj​>ai​}，则包含 $i$ 的合法子序列的结尾元素最远只能到 $x-1$。

发现，重要的不是值本身，而是大小关系。所有可以离散化。从小到大标号 $1\sim n$，权值小的放前面；权值相同下标大的放前面。

下面的 $a$ 均表示离散化后的序列。

同时将合法上升子序列拆分成正着以 $i$ 结尾的上升子序列和倒着以 $i$ 结尾的下降子序列两个部分，分别求出方案数后乘法原理即可。

$1\sim i$ 以 $i$ 结尾的上升子序列，在已经离散化后，预处理就非常简单了。树状数组维护 $f_i:i$ 结尾的上升子序列个数。

然后考虑 $x-1\sim i$ 以 $i$ 结尾的下降子序列。

因为每个 $i$ 对应的 $x$ 不一样，不能像预处理一样只扫描一遍整个 $1\sim n$，也不可能每次都去遍历这个区间。

不妨考虑转化成$n\sim i$ 以 $i$ 结尾的下降子序列个数减去以 $x$ 开头以 $i$ 结尾的个数。

$n\sim i$ 以 $i$ 结尾的下降子序列个数，预处理方法同上。

最后就只剩下以 $x$ 开头以 $i$ 结尾的下降子序列个数的计算了，开头和结尾都已经定了，是可做的。

设 y : a y = max ⁡ { a j   ∣   x < j ≤ n } y:a_y=\max\{a_j\ |\ x<j\le n\} y:ay​=max{aj​ ∣ x<j≤n}，即 $x$ 以后的后缀最大值的下标。

必然有 $a_y<a_i<a_x$。

也就是说，当我们利用栈维护出后缀最大值序列后，这个下降子序列的所有元素 $k$ 都满足$a_y<a_k<a_x$。

那么，我们可以对于维护出来的后缀最大值上的每个节点开一个 $\text{vector}$。

把所有满足上述限制的 $k$，全都挂在一个节点上。

暴力地按照预处理的计算方式，计算下降子序列个数。

因为每个 $i$ 只会挂在一个 $x$ 上面，所以时间复杂度是可以保证的。

code

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 300005
vector < int > v[maxn];
int T, n, top;
int id[maxn], t[maxn], a[maxn], f[maxn], g[maxn], h[maxn], s[maxn];

void clear() { for( int i = 1;i <= n;i ++ ) t[i] = 0; }
void Add( int i, int x ) { for( ;i <= n;i += i & -i ) ( t[i] += x ) %= mod; }
int Ask( int i ) { int ans = 0; for( ;i;i -= i & -i ) ( ans += t[i] ) %= mod; return ans; }

signed main() {
    scanf( "%lld", &T );
    while( T -- ) {
        top = 0; 
        for( int i = 1;i <= n;i ++ ) v[i].clear();
        scanf( "%lld", &n );
        for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] ), id[i] = i;
        sort( id + 1, id + n + 1, []( int x, int y ) { return a[x] == a[y] ? x > y : a[x] < a[y]; } );
        for( int i = 1;i <= n;i ++ ) a[id[i]] = i; //离散化
        clear();
        for( int i = 1;i <= n;i ++ ) Add( a[i], f[i] = Ask( a[i] ) + 1 );
        //f[i]:1~i以i结尾的上升子序列个数 
        //f[i]=1+\sum_{j=1}^{i-1}f[j](a_j<a_i)
        clear();
        for( int i = n;i;i -- ) Add( n - a[i] + 1, g[i] = Ask( n - a[i] + 1 ) + 1 );
        //g[i]:n~i以i结尾的下降子序列个数
        //g[i]=1+\sum_{j=n}^{i+1}g[j](a_j>a_i)
        for( int i = n;i;i -- ) if( a[i] > a[s[top]] ) s[++ top] = i;//后缀最大值的有用点
        for( int i = n;i;i -- ) { //必须倒序
            int l = 1, r = top, pos;
            while( l <= r ) {
                int mid = ( l + r ) >> 1;
                if( a[i] <= a[s[mid]] ) r = mid - 1, pos = mid;
                else l = mid + 1;
            }
            if( i ^ s[pos] ) v[pos].push_back( i );
            //将满足a_{s[pos-1]}<a_i<a_{s[pos]}的i归属于s[pos]集合
        }
        for( int i = 1;i <= n;i ++ ) t[i] = 0;
        for( int i = 1;i <= top;i ++ ) {
            Add( n - a[s[i]] + 1, h[s[i]] = 1 );
            //h[k]:k~k隶属的s[i] 以s[i]开始k结尾的下降子序列
            //h[k]=\sum_{j=k+1}^{s[i]}h[j](a_j>a_k)
            for( int k : v[i] ) Add( n - a[k] + 1, h[k] = Ask( n - a[k] + 1 ) );
            //所有下标>k的j都已经加入了 这也是为什么上面必须倒序储存
            //相当于clear() 但每次k数量很少 从1~n都清一遍浪费时间
            for( int k : v[i] ) Add( n - a[k] + 1, -h[k] );
            Add( n - a[s[i]] + 1, -1 );
        }
        int ans = 0;
        //g[i]-h[i]:合法的n~i以i结尾的下降子序列数量 f[i]:合法的1~i以i结尾的上升子序列数量
        for( int i = 1;i <= n;i ++ ) ( ans += ( g[i] - h[i] ) % mod * f[i] ) %= mod;
        printf( "%lld\n", ( ans + mod ) % mod );
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59