H城是一座小城市，前几日才刚刚建立公交系统，且只有一辆公交车。于是，如何最大化这唯一一辆公交车的载客量成了亟待解决的问题。
H城的俯视图可以近似地看成是一个棋盘网络——共有N行M列，从南向北，每行从1到M标号，从西向东，每列从1到N标号。经实地考察，公交总公司选定了K个可以设为站点的地方，其中第K个站点位于第Xi列，第Yi行，预计每天有Pi名乘客需要在此乘车。
设有序数对（X,Y）表示第X列，第Y行。每天，公交车从（1,1）开出，驶向（N,M），途中只能向北或向东行驶。
现在，公交总公司希望你能够帮助他们选定一条路线，使得能够接到的乘客数最大，我们假设公交车的容量无限大。
一个非负整数ans，表示最多能接到的乘客数。
若干行，对于每个询问输出’Yes’表示他们是亲戚，或’No’表示他们不是亲戚
8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
11
如果把每个点看成一个状态，F[x,y]表示最大人数，那么它只能从它下面或者左边的点转移过来，于是每次就是找到一个x,y都小于等于该点的最大的F[X,Y]。这实际上是一个加权LIS，但是权值和坐标值都很大，于是想到用分治代替平衡树的方法来维护。
我们先给x排序离散好，这里要满足x相等的点y小的在前面。然后把y快排好，进入分治。
对于每次分治[l,r]，我们的任务是用[l,mid]的F去更新[mid+1,r]的F(因为右半边的F值只受左半边的影响，大概类似NOI Cash那个题)。由于我们已经排好了y，那么分治的下标其实就是x，于是对于每个[l,r]过程，我们要把它按照x相对mid的大小分成两个部分[l,mid],[mid+1,r]，这两部分分别是y单增的。
然后，左半边[l,mid]维护一个y和F都单调增的数组，然后扫一遍右半边[mid+1,r]，找到不小于这个点y值得最靠右的一个F(也就是最大的F)，转移即可。
更新完F值，我们需要把分开的两部分合并起来，也就是归并排序，保证回溯到上一层的时候[l,r]仍然是y单增的。
需要注意的是，由于每次要拆了又合，所以F的下标很乱，不如直接把F记到每个点上，这样随着分治的过程，F值会始终跟着这个点分来分去。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 102000
using namespace std; struct point
{
int x,y,v,f;
}p[maxn],q[maxn],stack[maxn];
int f[maxn];
int nx,ny,n,ans; void solve(int l,int r)
{
if (l==r){
if (p[l].f==) p[l].f=p[l].v;
ans=max(ans,p[l].f);
return ;
}
int mid=(l+r)>>;
int l1=l,l2=mid+;
for (int i=l;i<=r;i++) if (p[i].x<=mid) q[l1++]=p[i]; else q[l2++]=p[i];
for (int i=l;i<=r;i++) p[i]=q[i];
solve(l,mid);
int top=;
for (int i=l;i<=mid;i++){
if (p[i].f>stack[top].f) stack[++top]=p[i];
}
int now=;
for (int i=mid+;i<=r;i++){
while (now<top&&stack[now+].y<=p[i].y) now++;
if (now) p[i].f=max(p[i].f,stack[now].f+p[i].v);
}
solve(mid+,r);
l1=l,l2=mid+;
for (int i=l;i<=r;i++)
if ((p[l1].y<=p[l2].y||l2>r)&&l1<=mid) q[i]=p[l1++]; else q[i]=p[l2++];
for (int i=l;i<=r;i++) p[i]=q[i];
} bool cmp1(point a,point b)
{
return (a.x<b.x)||(a.x==b.x&&a.y<b.y);
}
bool cmp2(point a,point b)
{
return a.y<b.y;
} int main()
{
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
scanf("%d%d%d",&nx,&ny,&n);
for (int i=;i<=n;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);
sort(p+,p+n+,cmp1);
for (int i=;i<=n;i++) p[i].x=i;
sort(p+,p+n+,cmp2);
solve(,n);
printf("%d\n",ans);
return ;
}
Bus