题意

给出一个序列的以每一项结尾的 \(LIS\) 的长度a[]，求一个序列，使得以每一项为开头的最长下降子序列的长度之和最大。

\(n\leq 10^5\) 。

分析

• 最优解一定是一个排列，因为如果两个数字的大小相同，完全可以区别他们的大小，以得到更多的贡献。

• 考虑的 \(a\) 给定的限制，显然对于所有的相同大小的 \(a\) ，前一项 \(a_{p_1}\) 要大于后一项 \(a_{p_2}\)，否则一定会产生更长的上升子序列。连边\(p_2\rightarrow p_1\)表示 \(p_2\) 的值小于\(p_1\)。

• 对于 \(i\)，找到上一次出现 \(a[i]-1\) 的位置，并连边 $ {pos}_{a[i]-1}\rightarrow i$ ，表示 \(i\) 要大于此位置的值。

• 然后进行贪心的操作，每次在所有入度为0的点中选择编号最大的并赋上最小的权值。确定数值之后依次确定 \(b\) 的值就好了。

• 正确性显然，因为对于相同的 \(a_x\) 来说我们会优先考虑最靠后的 \(last\)，同时靠前的不会向 \(last\) 后边连边。

• 总时间复杂度为 \(O(nlogn)\) ，主要是 \(BIT\) 的复杂度。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define fi first#define se second#define mp make_pair#define pb push_back#define rep(i,a,b) for(int i=a;i<=b;++i)#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)typedef long long LL;typedef pair
           
             pii;inline int gi(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*f;}template
            
             inline bool Max(T &a,T b){return a
             
              
               inline bool Min(T &a,T b){return a>b?a=b,1:0;}const int N=1e5 + 7;int n,edc;int head[N],ind[N],lst[N],a[N],b[N],f[N];struct edge{ int last,to; edge(){}edge(int last,int to):last(last),to(to){}}e[N*2];void Add(int a,int b){ e[++edc]=edge(head[a],b),head[a]=edc; ++ind[b];}int tr[N];int lowbit(int x){return x&-x;}void modify(int x,int y){for(int i=x;i<=n;i+=lowbit(i)) Max(tr[i],y);}int query(int x){int res=0;for(int i=x;i;i-=lowbit(i)) Max(res,tr[i]);return res;}priority_queue
               
                Q;void topo(){ rep(i,1,n) if(!ind[i]) Q.push(i);int tmp=0; while(!Q.empty()){ int u=Q.top();Q.pop(); b[u]=++tmp; go(u) if(--ind[v]==0) Q.push(v); }}int main(){ n=gi(); rep(i,1,n){ a[i]=gi(); if(lst[a[i]]) Add(i,lst[a[i]]); if(lst[a[i]-1]) Add(lst[a[i]-1],i); lst[a[i]]=i; } topo(); LL ans=0; for(int i=n;i;--i){ f[i]=query(b[i]-1)+1; modify(b[i],f[i]); ans+=f[i]; } printf("%lld\n",ans); return 0;}