P3970 [TJOI2014]上升子序列

传送门

上升子序列 就是满足严格递增

先考虑大体思路：

如果题目没有要求“如果两个上升子序列相同,那么只需要计算一次”，那么就非常友好了

dp转移方程也很简单 

dp[i]=Σdp[j](0<j<i)

但是现在要求相同的只能记一次

我们考虑用一个数组la（lastans）[]记录

那么这个数组的作用是什么呢？

在a[i]第一次出现时 我们记录下它前面有多少个上升子序列

即la[i]=子序列个数

在a[i]第二次出现时 仍然先计算它前面上升子序列的个数（假设为ans1） 

但因为其中有一部分已经在第一次遇到a[i]时求解过了

所以我们用ans1-la[a[i]] 

这就是第一个a[i]与第二个a[i]之间上升子序列的个数

具体细节：

如果用一般dp的方法求解 大概只能过前30%

对于100% 的数据 我们考虑用树状数组优化（安利）

这样复杂度可以从O(n^2)降到O(nlogn)

最后不要忘记离散化

具体看代码啦

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int mxn=1e5+5;
typedef long long ll;
ll a[mxn],b[mxn],ans;
int n,sz;
bool v[mxn];
ll ld[mxn],f[mxn];
ll lowbit(ll x){
    return x&(-x);
}
void motify(ll x,ll w){
    for(;x<=n;x+=lowbit(x)){
        f[x]=(f[x]+w)%mod;
    }
}
ll get(ll x){
    ll temp=0;
    for(;x;x-=lowbit(x)){
        temp=(temp+f[x])%mod;
    }
    return temp;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    sz=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+sz+1,a[i])-b;
    }
    ans=0;
    for(int i=1;i<=n;i++){
        if(!v[a[i]]){
            v[a[i]]=1;
            ll t=get(a[i]-1);
            ans=(ans+t)%mod;
            ld[a[i]]=t;
            motify(a[i],t+1);
            continue;
        }
        v[a[i]]=1;
        ll t=get(a[i]-1);
        ans=(ans+t-ld[a[i]]+mod)%mod;
        motify(a[i],(t-ld[a[i]]+2*mod)%mod);
        ld[a[i]]=t;
    }
    std::cout<<ans;
    return 0;
}