P3431 [POI2005]AUT-The Bus【树状数组+离散化】【二维偏序】

题意：

n*m的范围内有k个点
$1\le n\le 10^9,1\le m\le 10^9$1≤n≤109,1≤m≤109
你从(0, 0)出发到(n,m) 每次你只能往上或往右移动，求经历的路径最大点权值

思路:

也就是说我们要让点经历的 $x_i\le x_{i+1},y_i\le y_{i+1}$xi​≤xi+1​,yi​≤yi+1​
也就是二维偏序，求最大前缀和
先对y坐标排序,离散化
树状数组，区间修改 改成 维护最大前缀和 区间查询 改成查询最大前缀和
然后再对点根据x坐标排序

AC_code:

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int bit[MAXN];
int cnt = 0;
struct node {
	int x, y, val;
} p[MAXN];
bool cmp1(node aa, node bb) {
	return aa.y < bb.y;
}
bool cmp2(node aa, node bb) {
	if(aa.x == bb.x) {
		return aa.y < bb.y;
	}
	return aa.x < bb.x;
}
int lowbit(int x) {
	return x&(-x);
}
void add(int i,int x) {
	while(i<=cnt) {
// bit[i]+=x;
		bit[i] = max(bit[i], x);
		i+=lowbit(i);
	}
}
int sum(int i) {
	int s=0;
	while(i>0) {
// s+=bit[i];
		s = max(s, bit[i]);
		i-=lowbit(i);
	}
	return s;
}

int main() {
	int n, m, k;
	cin>>n>>m>>k;
	for(int i = 1; i <= k; i++) {
		scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].val);
	}
	//对y排序 离散化
	sort(p+1, p+1+k, cmp1);
	int now = p[1].y;
	p[1].y = ++cnt;
	for(int i = 2; i <= k; i++) {
		if(p[i].y != now) {
			now = p[i].y;
			p[i].y = ++cnt;
		} else {
			p[i].y = cnt;
		}
	}
	// 对x排序 再对y排序 左下优先
	sort(p+1, p+1+k, cmp2);
	int res;
	int ans = 0;//当前的最大前缀和
	for(int i = 1; i <= k; i++) {
		res = sum(p[i].y)+p[i].val;
		//cout<<res<<endl;
		add(p[i].y, res);
		ans = max(res, ans);
	}
	cout<<ans<<endl;

	return 0;
}