注意！！！ (1-h_{i-1}) 和 (h_{i+1}-n) 是可以有等于 (h_i) 的，翻译错了
为什么会有两个たのしい
Solution
考虑最后能够获得收入的位置，这些位置构成一个先上升再下降的序列。
那么我们可以枚举那个最高点，然后算出这个点左边递增的最大收入和右边递减的最大收入。
那么只考虑左边，右边同理即可。
我们设 (f_i) 表示拔完某些草（也就是已经减去 (c) ）之后，没有比 (i) 更高的草，剩余这些草的最大总收益。
那么可以得到转移方程：
(sumlimits_{j<k<iAnd h_k>h_i}c_k) 表示 (j) 到 (i) 这段中，只需要删去 (h_k>h_i) 的那一部分。
这样的时间复杂度是 (O(n^3)) 的，所以需要优化。
因为 (h_jleq h_i<h_k) ，所以可以看作 (h_k) 对 (h_j) 有一个 (-c_k) 的贡献，进而 (h_k) 对所有 (h_j<h_k) 的 (j) 的都有一份贡献，所以考虑以高度为下标开一颗线段树，维护区间最大值。
具体操作：对于 (i) ，每次查询 (max[0,h_i]) ，可得 (f_i=max[0,h_i]+p_i) ，然后拿 (f_i) 更新 (h_i) 位置，并对于 ([0,h_i-1]) 减去 (c_i) 。
可以看出 (max[0,h_i]) 就是转移方程中的 (maxlimits_{1leq j <iAnd h_jleq h_i}{f_j-sumlimits_{j<k<iAnd h_k>h_i} c_k}) 。因为当我们在操作 (j) 之后，每一个 (c_k(h_k>h_j)) 我们都已经减去。那么到了 (i) 的时候， ([0,h_i]) 上的点就是我们要求的，这个时候查询 (max) 即可。
那这个题的大体思路就没了。
小细节：因为 (h_ileq 10^9,nleq 10^5) ，所以如果以高度为下标建树是不行的，记得离散化。
Code
#include<bits/stdc++.h>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=1e5+10;
const ll INF=1e18;
int n,h[N],p[N],c[N],buk[N],lsh;
ll f[N],g[N],mx[N<<2],lz[N<<2],ans;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
void build(int rt,int l,int r){
mx[rt]=-INF; lz[rt]=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid); build(rs,mid+1,r);
}
inline void pushdown(int rt){
if(!lz[rt]) return ;
mx[ls]+=lz[rt]; lz[ls]+=lz[rt];
mx[rs]+=lz[rt]; lz[rs]+=lz[rt];
lz[rt]=0;
}
void update(int rt,int l,int r,int L,int R,ll v){
if(L<=l&&r<=R){
mx[rt]+=v; lz[rt]+=v;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid) update(ls,l,mid,L,R,v);
if(R>mid) update(rs,mid+1,r,L,R,v);
mx[rt]=max(mx[ls],mx[rs]);
}
ll query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R) return mx[rt];
pushdown(rt);
int mid=(l+r)>>1;
ll res=-INF;
if(L<=mid) res=max(res,query(ls,l,mid,L,R));
if(R>mid) res=max(res,query(rs,mid+1,r,L,R));
return res;
}
void insert(int rt,int l,int r,int p,ll v){
if(l==r){
mx[rt]=max(v,mx[rt]);
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(p<=mid) insert(ls,l,mid,p,v);
else insert(rs,mid+1,r,p,v);
mx[rt]=max(mx[ls],mx[rs]);
}
inline void work(ll *f){
build(1,0,lsh); insert(1,0,lsh,0,0);
for(int i=1;i<=n;i++){
f[i]=query(1,0,lsh,0,h[i])+p[i];
insert(1,0,lsh,h[i],f[i]);
update(1,0,lsh,0,h[i]-1,-c[i]);
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)
h[i]=read(),p[i]=read(),c[i]=read(),buk[++lsh]=h[i];
sort(buk+1,buk+lsh+1);
lsh=unique(buk+1,buk+lsh+1)-buk-1;
for(int i=1;i<=n;i++)
h[i]=lower_bound(buk+1,buk+lsh+1,h[i])-buk;
work(f);
reverse(h+1,h+n+1); reverse(p+1,p+n+1); reverse(c+1,c+n+1);
work(g);
reverse(g+1,g+n+1); reverse(p+1,p+n+1);
for(int i=1;i<=n;i++)
ans=max(ans,f[i]+g[i]-p[i]);
printf("%lld
",ans);
return 0;
}