正题
题目链接:https://www.luogu.com.cn/problem/P3971
题目大意
一个\(1\sim n\)的一个排列，设\(a_i\)表示以\(i\)结尾的最长上升子序列长度，\(b_i\)表示以\(i\)开头的最长下降子序列长度。
给出序列\(a\)求序列\(b\)的最大和。
\(1\leq n\leq 10^5\)
解题思路
考虑数组\(a\)带来的限制
- 对于一个\(a_i=a_j=w(i<j)\)那么有\(x_i>x_j\)
- 对于一个\(a_j=w+1\)前一个最近的\(a_i=w\)那么有\(x_i<x_j\)
第一个限制其实不用管，因为如果我们要最优，一定会满足那个限制。
考虑第二个限制，我们将\(i\)向\(j\)连一条边，这样我们就可以得到一棵树（把\(0\)视为虚根的话）。
那么我们子节点的权值一定要比父节点的大，然后在满足这个的前提下我们优先扩展编号大的节点就好了。
也就是从大到小跑一遍\(dfs\)序就可以得到\(x\)数组。
然后用树状数组统计一下答案。
时间复杂度\(O(n\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10;
struct node{
int to,next;
}a[N];
int n,tot,cnt,dfn[N],ls[N],t[N],las[N];
long long ans;
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs(int x){
dfn[x]=++cnt;
for(int i=ls[x];i;i=a[i].next)
dfs(a[i].to);
return;
}
void Change(int x,int val){
while(x<=n){
t[x]=max(t[x],val);
x+=lowbit(x);
}
return;
}
int Ask(int x){
int ans=0;
while(x){
ans=max(ans,t[x]);
x-=lowbit(x);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
addl(las[x-1],i);las[x]=i;
}
cnt=-1;dfs(0);
for(int i=n;i>=1;i--){
int t=Ask(dfn[i])+1;
ans+=t;
Change(dfn[i],t);
}
printf("%lld\n",ans);
return 0;
}