2019 Multi-University Training Contest 6 1005 Snowy Smile 线段树维护最大子段和

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans = 0;
int T;
int n;
const int maxn = 2e5+5;
struct point{
int x,y;
ll w;
}p[maxn];
int xx[maxn],yy[maxn];
int tot1,tot2;
struct tree{
int l,r;
ll sum,mxl,mxr,mxs;
}tr[maxn<<2];
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
void build(int now,int l,int r){
tr[now].l = l;
tr[now].r = r;
tr[now].sum = tr[now].mxs = tr[now].mxl = tr[now].mxr = 0;
if(l == r)
return;
int mid = (l + r) >> 1;
build(now<<1,l,mid);
build(now<<1|1,mid+1,r);
return;
}
void push_up(int now){
tr[now].sum = tr[now<<1].sum + tr[now<<1|1].sum;
tr[now].mxl = max(tr[now<<1].mxl,tr[now<<1].sum + tr[now<<1|1].mxl);
tr[now].mxr = max(tr[now<<1|1].mxr,tr[now<<1|1].sum + tr[now<<1].mxr);
tr[now].mxs = max(tr[now<<1].mxs,max(tr[now<<1|1].mxs,tr[now<<1].mxr + tr[now<<1|1].mxl));
return;
}
void update(int now,int pos,int val){
if(tr[now].l == tr[now].r){
tr[now].sum += val;
tr[now].mxl += val;
tr[now].mxr += val;
tr[now].mxs += val;
return;
}
int mid = (tr[now].l + tr[now].r) >> 1;
if(pos <= mid)update(now<<1,pos,val);
else update(now<<1|1,pos,val);
push_up(now);
return;
}
bool cmp(point a,point b){
return a.x < b.x;
}
int main(){
T = get_num();
while(T--){
ans = 0;
n = get_num();
for(int i = 1;i <= n;++i){
p[i].x = get_num();
p[i].y = get_num();
p[i].w = get_num();
xx[i] = p[i].x;
yy[i] = p[i].y;
}
sort(xx+1,xx+n+1);
sort(yy+1,yy+n+1);
tot1 = unique(xx+1,xx+n+1) - (xx+1);
tot2 = unique(yy+1,yy+n+1) - (yy+1);
for(int i = 1;i <= n;++i){
p[i].x = lower_bound(xx+1,xx+tot1+1,p[i].x) - xx;
p[i].y = lower_bound(yy+1,yy+tot2+1,p[i].y) - yy;
}
sort(p+1,p+n+1,cmp);
for(int i = 1;i <= tot1;++i){
build(1,1,tot2);
int l = 0;
for(int j = 1;j <= n;++j){
if(p[j].x == i){
l = j;
break;
}
}
int r = l;
for(int j = i;j <= tot1;++j){
for(;p[r].x <= j && r <= n;++r){
update(1,p[r].y,p[r].w);
}
ans = max(ans,tr[1].mxs);
}
}
printf("%lld\n",ans);
}
return 0;
}```

0 条评论