题意

pdf

题解

还不错的题啊。。
看了题解感觉并不难，没做出来很惭愧啊。。。。。
主要是被这种题目的形式吓到了。
然后一时间完全没有想法

首先，这种题一个显然的方向就是，你要使得b最大，肯定是尽量把大的数往前放
整道题就是围绕这个基础的了。。
所以可以得到一个很显然的结论，那就是$a[i]$肯定是由最后一个$a[i]-1$转移过来是最优的
然后得到这个结论以后，我们就让$a[i]-1$向$a[i]$连边
然后就可以得到一棵树
然后因为我们要使得大的数放在前面
所以对这棵树跑一次dfs序就是答案了
同时，如果说存在有多少$a[i]$相等，那么肯定是后面的$s[i]$大
然后用邻接表的话可以很简单地实现
最后再把b求出来就可以了

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100005;
int n;
int a[N];
int lst[N];
struct qq
{int x,y,last;
}e[N];int num,last[N];
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int cnt=0;
void dfs (int x)
{a[x]=cnt++;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;dfs(y);}
}
int f[N];
int lb (int x)  {
   return x&(-x);}
int get (int x)
{int mx=0;while (x>0){mx=max(mx,f[x]);x=x-lb(x);}return mx;
}
void change (int x,int y)
{while (x<=n){f[x]=max(f[x],y);x=x+lb(x);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d",&n);for (int u=1;u<=n;u++) {scanf("%d",&a[u]);init(lst[a[u]-1],u);lst[a[u]]=u;}dfs(0);memset(f,0,sizeof(f));long long ans=0;for (int u=n;u>=1;u--){int x=get(a[u]-1)+1;ans+=x;change(a[u],x);}printf("%lld\n",ans);return 0;
}