好羞愧啊最近一直在刷水。。。

题意：给定序列$c$的$a_i$,构造出一个序列$c$使得$\sum b_i$最大。

其中$a_i$表示以$c_i$结尾的最长上升子序列长度，$b_i$表示以$c_i$为开头的最长下降子序列长度。

首先$a_i = x$一定是从一个$a_j = x-1$转移而来的。这里让$a_i$从所有$a_j = x-1$的$a_j$里$c_j$最小的转移而来，一定不会有更优的转移。

因为这样它还可以和其它$a_j$做出至少1的贡献。那么我们由$i$向$j$连边。这样会形成一棵以0为根的树，后连边的点先遍历，令$c_j $等于dfs序。这样得到的序列就可以满足题意。求一遍$b$就行了。

#include
     
      using namespace std;const int N=100010;inline int read(){    int r=0,c=getchar();    while(!isdigit(c))c=getchar();    while(isdigit(c))    r=r*10+c-'0',c=getchar();    return r;}struct Edge{    int to,nxt;}e[N*2];int head[N],cnt=1;void add(int u,int v){    e[cnt]=(Edge){v,head[u]};    head[u]=cnt++;}int a[N],las[N],n,dc;void dfs(int u){    a[u]=++dc;    for(int i=head[u];i;i=e[i].nxt)    dfs(e[i].to);}int b[N],c[N];void upd(int x,int v){    for(int i=x;i<=n;i+=i&-i)    c[i]=max(c[i],v);}int ask(int x){    int ret=0;    for(int i=x;i;i-=i&-i)    ret=max(ret,c[i]);    return ret;}int main(){    n=read();    for(int i=1;i<=n;i++){        int x=read();        add(las[x-1],i);        las[x]=i;    }    dfs(0);    long long ans=0;    for(int i=n;i;i--){        b[i]=ask(a[i]-1)+1;        ans+=1ll*b[i];        upd(a[i],b[i]);    }    cout<