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

Translation

平面上有 N 个村庄，YJJ 经过第 k 个村庄可以得到 $v_k$ 的钱。 如果 XJJ 当前在 $(x,y)$，那么每一秒 TA 只能走到 $(x+1,y)$, $(x,y+1)$ 或者 $(x+1,y+1)$。 对于第 k 个村庄，其处于 $(x_k,y_k)$，只有 YJJ 从 $(x_k−1,y_k−1)$ 走来才可以得到 $v_k$ 的钱。 现在要求出 TA 最多可以得到多少钱。

Analysis

因为这种题目有横坐标、纵坐标两个约束变量，我们自然想到对横坐标进行排序； 排序之后我们只需要考虑 y 了。我们发现可以枚举一个村庄 $P(x,y)$，那么其左下角的所有村庄到 $P$ 都是可行的；所以我们需要求加和。树状数组或者线段树。 但是 y 又很大，所以先离散，再树状数组/线段树解决。注意这里要用到树状数组求区间最大值。

从 @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;
}