Description：

平面有 $N$ 个点，每个点都有个权值，选择一个点（可以不是原来的点），最大化到这个点的曼哈顿距离不超过 $K$ 的点的权值和。

$1\leqslant n\leqslant 10^6$

Solution：

曼哈顿距离是一个菱形肯定要先变成切比雪夫距离化成正方形，这样就变成了找一个边长为 $2K$ 的正方形使得被它框住的点权值和最大，这个可以扫描线 $+$ 线段树，线段树维护以这个位置为右上角时的权值和，按横坐标每次加入一个点，并在线段树上把能覆盖这个点的区间都加一，这些区间的位置一定也是一个区间，然后删除横坐标太靠前的点，最后更新答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 1000001

#define POS 2000002

#define NEG 1

struct point

{

	int x,y,v;

}p[MAXN];

bool cmp_x(point a,point b){return a.x < b.x;}

struct node

{

	int lc,rc;

	int maxv,tag;

}t[POS << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag != 0)

	{

		t[t[rt].lc].tag += t[rt].tag;t[t[rt].lc].maxv += t[rt].tag;

		t[t[rt].rc].tag += t[rt].tag;t[t[rt].rc].maxv += t[rt].tag;

		t[rt].tag = 0;

	}

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].maxv;

	int res = 0;

	pushdown(rt);

	if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int main()

{

	scanf("%d%d",&n,&k);

	int x,y;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d",&p[i].v,&x,&y);

		p[i].x = x + y;p[i].y = x - y + MAXN;

	}

	k = k * 2 + 1;

	sort(p + 1,p + 1 + n,cmp_x);

	build(root,NEG,POS);

	int ans = 0;

	for(int i = 1,j = 1;i <= n;++i)

	{

		for(;j < i && p[i].x - p[j].x > k - 1;++j)add(root,p[j].y,min(POS,p[j].y + k - 1),-p[j].v,NEG,POS);

		add(root,p[i].y,min(POS,p[i].y + k - 1),p[i].v,NEG,POS);

		ans = max(ans,query(root,NEG,POS,NEG,POS));

	}

	cout << ans << endl;

	return 0;

}