# HDU 6447 YJJ's Salesman 题解：排序+离散+树状数组

## Problem Description

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination. One day, he is going to travel from city $A$ to southeastern city $B$. Let us assume that A is $(0,0)$ on the rectangle map and $B (10^9,10^9)$. YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at $(x,y)$ now $(0\leqslant x\leqslant 10^9,0\leqslant y\leqslant 10^9)$, he will only forward to $(x+1,y)$, $(x,y+1)$ or $(x+1,y+1)$.

On the rectangle map from $(0,0)$ to $(10^9,10^9)$, there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village $k$ on $(x_k,y_k)$ $(1\leqslant x_k \leqslant 10^9,1\leqslant y_k\leqslant 10^9)$, only the one who was from $(x_k−1,y_k−1)$ to $(x_k,y_k)$ will be able to earn $v_k$ dollars.(YJJ may get different number of dollars from different village.)

YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.

## Input

The first line of the input contains an integer $T (1\leqslant T\leqslant 10)$,which is the number of test cases.

In each case, the first line of the input contains an integer $N (1\leqslant N\leqslant 10^5)$.The following $N$ lines, the $k$-th line contains 3 integers, $x_k,y_k,v_k (0\leqslant v_k\leqslant 10^3)$, which indicate that there is a village on $(x_k,y_k)$ and he can get $v_k$ dollars in that village.
The positions of each village is distinct.

## Output

The maximum of dollars YJJ can get.

## Sample Input

1
3
1 1 1
1 2 2
3 3 1

## Sample Output

3

## Analysis

@CaptainSlow 那里学来的奇技淫巧，用命名空间的确可以让你的代码看起来很高端，特别是像线段树、树状数组这样的算法写在一个 namespace 里……

## Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define CLEAR(_) memset(_,0,sizeof(_))
using namespace std;
const int maxn=200005;

int T,n,ans,f[maxn];
struct Village{
int x,y,ys,w;
};
vector <Village> a;

namespace SegmentTree{
int tree[maxn*4],tag[maxn*4];
inline void clear(){
CLEAR(tree);CLEAR(tag);
}
inline void push_down(int tl,int tr,int p){
int mid=((tr-tl)>>1)+tl;
tree[p<<1]=max(tree[p<<1],tag[p]);
tag[p<<1]+=tag[p];
tree[(p<<1)+1]=max(tree[(p<<1)+1],tag[p]);
tag[(p<<1)+1]+=tag[p];
tag[p]=0;
}
inline void update(int sl,int sr,int tl,int tr,int delta,int p){
if (sl<=tl&&sr>=tr){
tree[p]=max(tree[p],delta);
tag[p]+=delta;
return;
}
push_down(tl,tr,p);
int mid=((tr-tl)>>1)+tl;
if (sl<=mid) update(sl,sr,tl,mid,delta,p<<1);
if (mid<sr)  update(sl,sr,mid+1,tr,delta,(p<<1)+1);
tree[p]=max(tree[p<<1],tree[(p<<1)+1]);
}
inline int query(int sl,int sr,int tl,int tr,int p){
if (sl>sr) return 0;
if (sl<=tl&&sr>=tr) return tree[p];
int ret=0;
push_down(tl,tr,p);
int mid=((tr-tl)>>1)+tl;
if (sl<=mid) ret=max(ret,query(sl,sr,tl,mid,p<<1));
if (mid<sr)  ret=max(ret,query(sl,sr,mid+1,tr,(p<<1)+1));
return ret;
}
}

inline void init(){
ans=0;
a.clear();CLEAR(f);
SegmentTree::clear();
}

inline bool compare_x(Village aa,Village bb){
return (aa.x<bb.x)||((aa.x==bb.x)&&(aa.y>bb.y));
}
inline bool compare_y(Village aa,Village bb){
return aa.y<bb.y;
}

/*
* 要先对 y 坐标离散化，不然没法搞
*/
inline void discrete(){
sort(a.begin(),a.end(),compare_y);
int cnt=0;
for (int i=0;i<a.size();i++){
cnt+=(bool)((i==0)||(a[i].y!=a[i-1].y));
a[i].ys=cnt;
}
}

int main(){
scanf("%d",&T);
while (T--){
init();
scanf("%d",&n);
for (int i=0;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a.push_back((Village){x,y,0,z});
}
discrete();
sort(a.begin(),a.end(),compare_x);
for (int i=0;i<n;i++){
f[i]=a[i].w+SegmentTree::query(1,a[i].ys-1,1,n*2,1);
// printf("F[%d]=%d\n",i,f[i]);
ans=max(ans,f[i]);
SegmentTree::update(a[i].ys,a[i].ys,1,n*2,f[i],1);
}
printf("%d\n",ans);
}
return 0;
}

# Related posts

POJ 3977 Subset 题解：折半搜索+二分查找