链接：

　　

题意：

　　左上角(0,0)，右下角(10^9,10^9)的网格，其中有n(1<=n<=10^5)个方格内有权值。

　　一次只能沿右，下，右下三个方向走一个格子，只有沿右下方向走到格子里才可以获得权值。

　　问从(0,0)到(10^9,10^9)的路径最大权值是多少。

思路：

　　网格路径权值问题，第一感考虑DP，x从上往下,y从左往右刷表,状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+w[i][j]).

　　存在两个问题：

　　(1)坐标范围10^9,数组开不下

　　　　离散化把坐标映射到[1,n]，比如一维数组{1,100,10,10}，先排序{1,10,10,100},然后离散化成{1,2,2,3}。

　　(2)n的范围为1e5，O(n^2)的DP时空复杂度均爆表。

　　　　联想背包问题的滚动数组，实际上我们可以只开一维数组，此时y需要从右往左刷表，状态转移方程为dp[j]=max(dp[j],dp[k]+w[i][j])，

　　　　dp[k]是区间[1,j-1]最大值，区间最值查询显然可以用线段树以O(logn)的复杂度来处理，总体复杂度O(nlogn)。

　　比赛时我怎么做不出来呢?菜到自闭orz~

代码：

1 #include
     
        2 #define rep(i,a,b) for (int i=a;i<=b;i++)  3 using namespace std;  4   5 const int MAXN=(int)1e5+10;  6   7 struct Point{  8   int x,y,w;  9 } p[MAXN]; 10 int posHash[MAXN]; 11 void initHash(int n); 12  13 struct Node{ 14   int l,r,val; 15 } tree[MAXN*4]; 16 void build(int id,int l,int r); 17 void update(int id,int pos,int w); 18 int query(int id,int L,int R); 19  20 int main() 21 { 22   int T; 23   cin>>T; 24   while (T--) { 25     int n; 26     scanf("%d",&n); 27     rep(i,0,n-1) { 28     scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w); 29     } 30  31     initHash(n); 32     build(1,1,n); 33  34     int sum=0; 35     rep(i,0,n-1) { 36       int temp=p[i].w; 37       if (p[i].y!=1) { 38         temp+=query(1,1,p[i].y-1); 39       } 40       update(1,p[i].y,temp); 41       sum=max(sum,temp); 42     } 43  44     printf("%d\n",sum); 45   } 46   return 0; 47 } 48  49 void initHash(int n) 50 { 51   sort(p,p+n,[](const Point &a,const Point &b) 52              {
   return a.x
      
       b.y : a.x