题目链接：POI2005-AUT-The Bus

题意：

一个街区，有n条南北干道，m条东西干道，一辆公交从左下角出发，只能向北或者向东开，每个十字路口有一定的人数，问最多能接到多少乘客。

题解：

二维偏序问题。

先把第二维离散化，然后以第一维排序，第二维用树状数组维护，每个点队答案的贡献为$max(val[1],val[2],···,val[a[i].y])+a[i].v$，然后该点队后面点的影响$val[i]=max(val[i],res[i])$。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int n, m, k;
struct NODE
{
    int x, y, val;
    NODE() {}
    NODE(int x, int y, int val)
    {
        this->x = x, this->y = y, this->val = val;
    }
} a[MAXN];
int Y[MAXN];
struct BIT
{
    ll c[MAXN];
    int n;
    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            c[i] = 0;
        this->n = n;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void update(int x, ll val)
    {
        while (x <= n)
        {
            c[x] = max(c[x], val);
            x += lowbit(x);
        }
    }
    ll query_max(int x)
    {
        ll ret = 0;
        while (x)
        {
            ret = max(ret, c[x]);
            x -= lowbit(x);
        }
        return ret;
    }
} bit;
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= k; i++)
    {
        int x, y, val;
        scanf("%d%d%d", &x, &y, &val);
        a[i] = NODE(x, y, val);
        Y[i] = y;
    }
    sort(Y + 1, Y + 1 + k);
    m = unique(Y + 1, Y + 1 + k) - Y - 1;
    // for (int i = 1; i <= Ycnt; i++)
    //     printf("%d ", Y[i]);
    for (int i = 1; i <= k; i++)
        a[i].y = lower_bound(Y + 1, Y + 1 + m, a[i].y) - Y;
    sort(a + 1, a + 1 + k, [](NODE x, NODE y) { return (x.x == y.x) ? x.y < y.y : x.x < y.x; });
    bit.init(m);
    ll ans = 0;
    for (int i = 1; i <= k; i++)
    {
        ll res = bit.query_max(a[i].y) + a[i].val;
        ans = max(ans, res);
        bit.update(a[i].y, res);
    }
    printf("%lld\n", ans);
    return 0;
}