• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 洛谷 P3970 [TJOI2014]上升子序列 题解

4小时前 2次浏览

[dp_i=1+sum_{j=1}^{i-1}dp_j[a_j<a_i]
]

``````// By: Little09
// Problem: P3970 [TJOI2014]上升子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3970
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
const ll mod=1000000007;
const int N=500005;
ll tree[N];
ll a[N],b[N],dp[N];
int used[N],pre[N];
int cnt;
map<int,int>q;
inline int lowbit(int x)
{
return x&(-x);
}
{
for (;x<=n;x+=lowbit(x)) tree[x]=(k+tree[x])%mod;
}
{
ll ans=0;
for (;x;x-=lowbit(x)) ans=(tree[x]+ans)%mod;
return ans;
}
{
int F=1,ANS=0;
char C=getchar();
while (C<'0'||C>'9')
{
if (C=='-') F=-1;
C=getchar();
}
while (C>='0'&&C<='9')
{
ANS=ANS*10+C-'0';
C=getchar();
}
return F*ANS;
}
int main()
{
sort(b+1,b+n+1);
for (int i=1;i<=n;i++)
{
if (i==1||b[i]!=b[i-1]) q[b[i]]=++cnt;
}
for (int i=1;i<=n;i++)
{
int u=q[a[i]];
pre[i]=used[u];
a[i]=u;
used[u]=i;
}
dp[1]=1;
for (int i=2;i<=n;i++)
{
if (pre[i]==0)
{
}
else
{