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
|
using namespace std;
#define ll long long
const int maxn=10000+10;
const int maxm=20000+10;
struct {
ll x,y,w;
}p[maxn];
ll t,q,n,m,N,a[maxn],b[maxn];
ll pre[maxm],nxt[maxm],s[maxm],tree[maxm];
bool cmp(node i,node j){return i.x<j.x; }
void init(){ N=1; while(N<m) N*=2; }
void build(){
for(int i=0;i<N*2;i++) pre[i]=nxt[i]=s[i]=tree[i]=0;
}
void update(ll k,ll x){
k+=N-1;
s[k]+=x;
if(s[k]>0) pre[k]=nxt[k]=tree[k]=s[k];
else pre[k]=nxt[k]=tree[k]=0;
while(k){
k=(k-1)/2;
s[k]=s[k*2+1]+s[k*2+2];
pre[k]=max(pre[k*2+1],s[k*2+1]+pre[k*2+2]);
nxt[k]=max(nxt[k*2+2],s[k*2+2]+nxt[k*2+1]);
tree[k]=max(max(tree[k*2+1],tree[k*2+2]),nxt[k*2+1]+pre[k*2+2]);
}
}
void solve(){
ll ans=0;
ll i,j,k;
for(i=1;i<=q;i++){
if(i==1 || p[i].x!=p[i-1].x){
build();
for(j=i;j<=q;j=k){
for(k=j;k<=q && p[j].x==p[k].x;k++) update(p[k].y,p[k].w);
ans=max(ans,tree[0]);
}
}
}
printf("%lldn",ans);
}
int main()
{
scanf("%lld",&t);
while(t--){
scanf("%lld",&q);
for(int i=1;i<=q;i++){
scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w);
a[i]=p[i].x;b[i]=p[i].y;
}
sort(a+1,a+q+1);n=unique(a+1,a+q+1)-(a+1);
sort(b+1,b+q+1);m=unique(b+1,b+q+1)-(b+1);
for(int i=1;i<=q;i++){
p[i].x=lower_bound(a+1,a+n+1,p[i].x)-a-1;
p[i].y=lower_bound(b+1,b+m+1,p[i].y)-b-1;
}
sort(p+1,p+q+1,cmp);
init();
solve();
}
return 0;
}
|
近期评论