描述
平面上有 N 处宝藏，第 ii 处位于点 (Xi,Yi) ，价值 Vi
你从点 (1,1)出发，只能向右或向上走（横纵坐标增加）
当你走到一处宝藏，你就会获得它，求最大的总收益（所获得的宝藏价值和）。
注意，可能有宝藏位于同一点，到达该点时获得位于该点的所有宝藏，不能放弃获得宝藏。
输入
第一行一个正整数，为宝藏个数
接下来 N 行，每行三个正整数，Xi,Yi,Vi
输出
一行一个数，为最大的价值和
样例
input
3
1 1 2
1 3 5
2 1 7
output
9
范围
50% N≤1000
90% N≤1e5
100% N≤1e6, 1≤ 输入中所有数 ≤1e8
限制
1s 128M
根据题目，我们只能向右向上走,显然我们的路径要满足任意 xj<=xi,yj<=yi (i<j)，发现满足单调递增，所以我们可以用类似最长上升子序列的思路来考虑，首先我们将横坐标排序，那我们就不用再考虑它了，对于纵坐标，我们只关心它们的相对大小，所以可以进行离散化。
定义fi表示以i结尾的最长上升子序列，fi由前边满足单调条件的最大f转移而来，那，我们可以使用树状数组维护这个最大值，具体而言，我们需要以纵坐标位值域，维护f的最大值，每次转移之后，将现在的点加入即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long LL;
LL n;
struct edge
{
LL x,y;
LL z;
}s[N];
bool cmp(edge a,edge b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
LL b[N];
LL h[N];
LL lowbit(int x){return x&(-x);}
void updata(int x,int y)
{
LL lx, i;
while (x <= n)
{
h[x] = y;
lx = lowbit(x);
for (i=1; i<lx; i<<=1)
h[x] = max(h[x], h[x-i]);
x += lowbit(x);
}
}
LL query(LL x)
{
LL ans = 0;
for (;x;x-= lowbit(x)) ans = max(h[x], ans);
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i].x>>s[i].y>>s[i].z;
}
sort(s+1,s+1+n,cmp);
for(int i=1;i<=n;i++) b[i]=s[i].y;
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) s[i].y=lower_bound(b+1,b+1+n,s[i].y)-b;
LL ans=0;
for(int i=1;i<=n;i++)
{
LL t = 0;
t = 1LL*query(s[i].y) +s[i].z;
updata(s[i].y,t);
ans = max(ans,t);
}
printf("%lld",ans);
return 0;
}