先将 \(a[i]\) 离散化。
设 \(f[i]\) 表示以数字 \(i\) 结尾的上升子序列数量。
则有 \(f[i]=\sum_{j=1}^{i-1}f[j]\)。
考虑用线段树实时维护 \(f[j]\)，就可以 \(logn\) 查询。
扫一遍整个序列，因为不能算重复，所以 \(ans\) 先减去上一次见到 \(a[i]\) 时的贡献 \(f[a[i]]\)，再在线段树查询区间得到此时的 \(f[a[i]]\)，将 \(ans\) 加上此时的 \(f[a[i]]\)，最后在线段树更新此时 \(f[a[i]]\)，时间复杂度 \(O(nlogn)\)。
#include<bits/stdc++.h>
#define mod 1000000007
#define N 100001
#define ll long long
using namespace std;
ll n,a[N],b[N],tr[N<<2],f[N],num,ans;
ll ask(ll rt,ll l,ll r,ll x,ll y){if(x>y)return 0;
if(x<=l&&r<=y)return tr[rt];
ll mid=(r+l)>>1,sum=0;
if(mid>=x)sum=(sum+ask(rt<<1,l,mid,x,y))%mod;
if(mid<y)sum=(sum+ask(rt<<1|1,mid+1,r,x,y))%mod;
return sum;
}
void add(ll rt,ll l,ll r,ll x,ll d){if(l==r){tr[rt]=d;return;}
ll mid=(r+l)>>1;
if(mid>=x)add(rt<<1,l,mid,x,d);
else add(rt<<1|1,mid+1,r,x,d);
tr[rt]=(tr[rt<<1]+tr[rt<<1|1])%mod;
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
sort(b+1,b+n+1),num=unique(b+1,b+n+1)-b-1;
for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+num+1,a[i])-b;
ans=(ans-f[a[i]]+mod)%mod,f[a[i]]=ask(1,1,num,1,a[i]-1),add(1,1,num,a[i],f[a[i]]+1),ans=(ans+f[a[i]])%mod;
}
cout<<ans;
}