题意分析
给定一个序列，求最大上升子序列和。注意不是最长上升子序列。
我们可以很容易得出一个 $\mathcal O(n^2)$ 的做法：枚举 $i\in [1,n]$ 和 $j \in [1,i-1]$，以 $a_i$ 为末尾的最大上升子序列和 $\textit{dp}_i$ 即满足 $a_j<a_i$ 的最大的 $\textit{dp}_j+a_i$。
然而 $1\leq n \leq 10^5$，$\mathcal O(n^2)$ 并不足以支持我们通过此题。
考虑优化。
能够使 $\textit{dp}_i=\textit{dp}_j+a_i$ 成立的 $j$ 需要满足以下条件：
- $j<i$；
- $a_j<a_i$；
- $\textit{dp}_j$ 最大。
我们想到使用数据结构来维护其中的某一个（些），使用另一个（些）来查询。
对于 $\textit{dp}_j$ 最大，明显想到区间最值。
对于 $a_j<a_i$，想到值域。
因此，我们可以通过权值树状数组来维护区间最值，每次查询即在 $[1,a_i-1]$ 内查询最大的 $\textit{dp}$ 值即可。
具体而言，令 $\textit{dp}_i$ 表示以 $a_i$ 结尾的最长上升子序列的和，权值树状数组 $t$ 维护在值域上由 $a_i$ 映射而得的 $\textit{dp}_i$。
注意需要离散化和 long long。
时间复杂度：$\mathcal O(n\log n)$。
为什么此处能够通过树状数组维护区间最值
众所周知，树状数组不能维护区间最值，因为区间最值不可差分。
也就是知道 $[1,r]$ 和 $[1,l-1]$ 的最值，不能求出 $[l,r]$ 的最值。
然而，此处并不需要差分，每次查询都是 $[1,r]$ 的形式，因此可以使用。
细节见代码。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
typedef long long ll;
const int N=1e5;
int n,a[N+1],tmp[N+1];
ll dp[N+1];
struct tree{
ll t[N+1];
int lowbit(int x){
return x&-x;
}
ll query(int x){
ll ans=0;
while(x){
ans=max(ans,t[x]);//不同之一
x-=lowbit(x);
}return ans;
}//注意这里是直接赋值，而不是传统的增加
void set(int x,ll k){
ll pl=k;
while(x<=N){
pl=max(pl,t[x]);//不同之二
t[x]=pl;
x+=lowbit(x);
}
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
tmp[i]=a[i];
}
sort(tmp+1,tmp+n+1);
int m=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(tmp+1,tmp+m+1,a[i])-tmp;
}
ll Max=0;
for(int i=1;i<=n;i++){
dp[i]=t.query(a[i]-1)+tmp[a[i]];
Max=max(Max,dp[i]);
t.set(a[i],dp[i]);
}printf("%lld\n",Max);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
