HDU-6447 YJJ's Salesman(线段树区间最大值优化DP&vector去重离散化)

题意：有一个1e9*1e9的地图，从0，0开始走，只能向右，向下，向右下三种行走方式。地图上有n个坐标有权值val，若能通过向右下行走的方式达到这些坐标，就能收获val的积分。问走到最后获得的最大积分是多少。

首先想到的是一个动态规划求最大收获。递推式即dp【i】【j】=max（dp【0~i-1】【0~j-1】）+val【i】【j】。
在该坐标的左上角区域内的任意一个位置取一个最大值继承。这就形成了一个找二维区间最大值的问题。但是仔细一想是否真的是二维的？

首先我们对于地图的遍历顺序是从上到下从左到右递推。那么当要计算第i行第j列的值时，因为遍历过了该行上方的每一行即0~i-1，并且没有对i以下行数据进行遍历和处理。因此行是一直都限定好是遍历不到后面的位置的。查询区间最大值时就不会超过i，那么很明显就是对j-1列进行一维区间最大值的查询，用线段树进行处理。

还有一个问题是若从左到右遍历一行，那么低位列先被更新一个最大值。这样会出现的问题是，之后的列在通过线段树查询区间最大值是会通过同行列的数据传递过来，这是不合理的。为了避免这种情况，我们从后往前遍历j，并更新线段树，就不会影响，因为更改的值在查询区间之外。

其次，对于线段树的更新，我们每次都用一个继承过来的值加上新村庄的值，再单点更新回线段树。这样是能保证线段树中每列的值是不断变大的。因为我们每次都是去区间内最大值加上某个值，再去更新某一列，覆盖掉的该列的值必定小于新值。

最后，因为地图是1e9*1e9的，村庄只有1e5个，因此要做一个离散化。这里用vetcor去重离散化的模板。首先记录下每个坐标，然后对坐标排序，我们需要的是坐标排序后的下标，这就是坐标之间的相对大小，然后对于主要存储坐标的数组进行值的离散化后的更新。
一个坐标x原值，映射到该x在排序后数组中的下标值。通过二分排序数组找到下标值，之间赋值给存储坐标数组的x，就是离散化后的坐标值。

#include<bits/stdc++.h>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
#define pb(x) push_back(x)
using namespace std;
const int maxn=1e5+7;
int t,n;
struct point///坐标值
{
    int x,y,w;
    bool operator <(const point &a)const
    {
        return x==a.x? y>a.y: x<a.x;///对于坐标的排序，即遍历顺序，先对行从上到下排序，之后对列从右到左排序
    }
    point(int a,int b,int c)
    {
        x=a,y=b,w=c;
    }
};
struct node///线段树
{
    int l,r,ma;
}tre[maxn<<2];
void push_up(int rt)
{
    tre[rt].ma=max(tre[rt<<1].ma,tre[rt<<1|1].ma);
}
void build(int l,int r,int rt)
{
    tre[rt].l=l,tre[rt].r=r;
    if(l==r)tre[rt].ma=0;
    else
    {
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        push_up(rt);
    }
}
void update(int pos,int val,int rt)
{
    if(tre[rt].l==pos&&tre[rt].r==pos) tre[rt].ma=val;
    else
    {
        int mid=(tre[rt].l+tre[rt].r)>>1;
        if(pos>mid) update(pos,val,rt<<1|1);
        else if(pos<=mid)update(pos,val,rt<<1);
        push_up(rt);
    }
}
int query(int l,int r,int rt)
{
    if(tre[rt].l>=l&&tre[rt].r<=r)return tre[rt].ma;
    else
    {
        int mid=(tre[rt].l+tre[rt].r)>>1;
        if(l>mid)return query(l,r,rt<<1|1);
        else if(r<=mid)return query(l,r,rt<<1);
        else return max(query(l,r,rt<<1|1),query(l,r,rt<<1));
    }
}
vector<point>q;
vector<int>xx,yy;
int main()
{
    int x,y,w;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        q.clear();
        xx.clear();
        yy.clear();
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&w);
            q.pb(point(x,y,w));
            xx.pb(x);
            yy.pb(y);
        }
        sort(xx.begin(),xx.end());///离散化
        sort(yy.begin(),yy.end());///先将坐标值按大小排序，得到每个坐标值的相对位置，也就是离散化映射的值
        xx.erase(unique(xx.begin(),xx.end()),xx.end());///去重，如果是相同坐标有区分则不能这样离散
        yy.erase(unique(yy.begin(),yy.end()),yy.end());
        for(int i=0;i<q.size();i++)
        {
            q[i].x=lower_bound(xx.begin(),xx.end(),q[i].x)-xx.begin();///映射下标到真实坐标上
            q[i].y=lower_bound(yy.begin(),yy.end(),q[i].y)-yy.begin();
        }
        sort(q.begin(),q.end());///排序成遍历顺序
        build(0,n,1);
        for(int i=0;i<q.size();i++)
        {
            int sum=0;
            if(q[i].y==0)sum=q[i].w;
            else sum=query(0,q[i].y-1,1)+q[i].w;
            update(q[i].y,sum,1);
        }
        printf("%d\n",query(0,n,1));
    }
}