P3970 [TJOI2014] 上升子序列

题目

先将 \(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;
}