P1637 三元上升子序列(DP+离散化权值树状数组)

传送门

思路：
方法1： $dp+$ 离散化转权值树状数组。

显然可以设 $dp[i][j]$ 为长度为 $i$ 以 $a[j]$ 结尾的子序列的个数。

有转移方程： $dp[i][j]=\sum\limits_{k<j,a[k]<a[j]} dp[i-1][k]$

显然暴力时间复杂度： $O(n^2m)$

因为 $a[i]\leq2^{63}$ ,但 $n\leq 3e4$ 考虑离散化 $a[i]$ ，然后转权值线段树储存 $dp[i-1][k]$ 。

先初始化一元上升子序列，然后从前往后遍历，

有转移方程： $dp[i][j]+=query(a[j]-1)$

再更新 $update(a[j],dp[i-1][j])$ 。

时间复杂度： $O(nmlogn)$ , $m$ 是几元上升子序列。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
typedef long long ll;
const int N=3e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m;
ll a[N],b[N],tr[N];
ll dp[4][N];
#define lowbit(x) x&(-x)
void update(int x,int k){
    while(x<=m){
        tr[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x){
    ll ans=0;
    while(x){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){    
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]),b[i]=a[i];
        dp[1][i]=1;
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=2;i<=3;i++){
        mst(tr);
        for(int j=1;j<=n;j++)
        {
            dp[i][j]+=query(a[j]-1);
            update(a[j],dp[i-1][j]);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=dp[3][i];
    printf("%lld\n",ans);
    return 0;
}

方法2：离散化树状数组+乘法原理。
显然可以枚举中间的数 $a[i]$ ，
根据乘法原理： $a[i]$ 贡献为 $cnt_{lower}[i]\times cnt_{upper}[i]$ 。
数据较大，离散化处理一下，用树状数组正反跑两遍即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e4+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
#define lowbit(x) x&(-x)
int n,a[N],b[N],m,cnt[N],tr[N];
void update(int x,int k){
    while(x<=m){
        tr[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x){
    ll ans=0;
    while(x){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]),b[i]=a[i];
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    ll ans=0;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=1;i<=n;i++){
        cnt[i]=query(a[i]-1);
        update(a[i],1);
    }
    mst(tr);
    for(int i=n;i>=1;i--){
         update(a[i],1);
         ans+=1LL*cnt[i]*(n-i+1-query(a[i]));
    }
    printf("%lld\n",ans);
    return 0;
}