题意
给出一个序列的以每一项结尾的 (LIS) 的长度a[]，求一个序列，使得以每一项为开头的最长下降子序列的长度之和最大。
(nleq 10^5) 。
分析
-
最优解一定是一个排列，因为如果两个数字的大小相同，完全可以区别他们的大小，以得到更多的贡献。
-
考虑的 (a) 给定的限制，显然对于所有的相同大小的 (a) ，前一项 (a_{p_1}) 要大于后一项 (a_{p_2})，否则一定会产生更长的上升子序列。连边(p_2 ightarrow p_1)表示 (p_2) 的值小于(p_1)。
-
对于 (i)，找到上一次出现 (a[i]-1) 的位置，并连边 $ {pos}_{a[i]-1} ightarrow i$ ，表示 (i) 要大于此位置的值。
-
然后进行贪心的操作，每次在所有入度为0的点中选择编号最大的并赋上最小的权值。确定数值之后依次确定 (b) 的值就好了。
-
正确性显然，因为对于相同的 (a_x) 来说我们会优先考虑最靠后的 (last)，同时靠前的不会向 (last) 后边连边。
-
总时间复杂度为 (O(nlogn)) ，主要是 (BIT) 的复杂度。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<queue>
#include<vector>
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<int,int> 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<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>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<int>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
",ans);
return 0;
}