题面
平面上有 \(n\) 个点，第 \(i\) 个点的坐标为 \((x_i,y_i)\)，权值为 \(w_i\)。编号不同的点可能重合，且 \(w_i\) 可能是负数。
现在你要选择 \(3\) 个整数 \(l,r,k\)，并取走所有满足 \(l\le x_i\le r,y_i\le k\) 的点。问对于所有可能的情况，你取走的点的权值和的最大值。
对于所有数据，\(1\le n\le 2.5\times10^5，1\le x_i,y_i,|w_i|≤10^9\)。
题解
考虑枚举 \(k\)，然后这是我们需要单点修改，求最大子段和。线段树维护即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2.5e5+5;
struct dian{
int x,y,w;
bool operator<(const dian&d)const{
return y<d.y;
}
}p[N];
int n,lsh[N];
LL s[N],ans;
struct node{
LL ls,rs,s,ans;
node operator+(const node&n)const{
return (node){max(ls,s+n.ls),max(n.rs,n.s+rs),s+n.s,max({ans,n.ans,rs+n.ls})};
}
}tr[N<<2];
int read()
{
int s=0,fl=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
fl=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s*fl;
}
void upd(int o,int l,int r,int x,LL y)
{
if(l==r)
{
tr[o].s=y;
tr[o].ls=tr[o].rs=tr[o].ans=max(y,0LL);
return;
}
int md=l+r>>1;
if(md>=x)
upd(o<<1,l,md,x,y);
else
upd(o<<1|1,md+1,r,x,y);
tr[o]=tr[o<<1]+tr[o<<1|1];
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
p[i].x=read(),p[i].y=read(),p[i].w=read(),lsh[i]=p[i].x;
sort(lsh+1,lsh+n+1);
for(int i=1;i<=n;i++)
p[i].x=lower_bound(lsh+1,lsh+n+1,p[i].x)-lsh;
sort(p+1,p+n+1);
for(int l=1;l<=n;)
{
int r=l;
while(r<=n&&p[r].y==p[l].y)
{
s[p[r].x]+=p[r].w;
upd(1,1,n,p[r].x,s[p[r].x]);
++r;
}
l=r;
ans=max(ans,tr[1].ans);
}
printf("%lld",ans);
}