Go(1.14.4) 解法, 执行用时: 444ms, 内存消耗: 41156K, 提交时间: 2020-07-30 23:27:58

package main

import . "nc_tools"

// github.com/EndlessCheng/codeforces-go
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type seg []struct{ l, r, max int }

func (t seg) build(o, l, r int) {
	t[o].l, t[o].r = l, r
	if l == r {
		return
	}
	m := (l + r) >> 1
	t.build(o<<1, l, m)
	t.build(o<<1|1, m+1, r)
}

func (t seg) update(o, i, v int) {
	if t[o].l == t[o].r {
		t[o].max += v
		return
	}
	if i <= (t[o].l+t[o].r)>>1 {
		t.update(o<<1, i, v)
	} else {
		t.update(o<<1|1, i, v)
	}
	t[o].max = max(t[o<<1].max, t[o<<1|1].max)
}

func BoomKill(n, m int, players []*Point) (ans int) {
	m--
	gx := [2e5 + 1][]int{}
	for _, p := range players {
		gx[p.X] = append(gx[p.X], p.Y)
	}
	t := make(seg, 4*n)
	t.build(1, 1, n)
	for i := 1; i <= m; i++ {
		for _, y := range gx[i] {
			t.update(1, y, 1)
		}
	}
	for i := 1; i <= n; i++ {
		if i-m-1 > 0 {
			for _, y := range gx[i-m-1] {
				t.update(1, y, -1)
			}
		}
		if i+m <= n {
			for _, y := range gx[i+m] {
				t.update(1, y, 1)
			}
		}
		for _, y := range gx[i] {
			t.update(1, y, -1)
		}
		ans = max(ans, len(gx[i])+t[1].max)
		for _, y := range gx[i] {
			t.update(1, y, 1)
		}
	}
	return
}

C++11(clang++ 3.9) 解法, 执行用时: 209ms, 内存消耗: 21020K, 提交时间: 2020-08-09 11:17:32

class Solution
{
	public:
		const static int N=2e5+7;
		int bit=1;
		int mx[N<<2];
		vector<int> ve[N];
		inline void Insert(int k,int val)
		{
			for(auto y:ve[k])
			{
				int p=y+bit;
				mx[p]+=val;
				for(p>>=1;p;p>>=1)
				mx[p]=max(mx[p<<1],mx[p<<1|1]);
			}
		}
		int BoomKill(int n,int m,vector<Point> &p)
		{
			for(;bit<=n+1;bit<<=1);
			int ans=0;
			for(int i=0;i<p.size();++i)
			ve[p[i].x].push_back(p[i].y);
			for(int i=1;i<m;++i)
			Insert(i,1);
			for(int i=1;i<=n;++i)
			{
				if(i+m-1<=n)
				Insert(i+m-1,1);
				if(i-m>0)
				Insert(i-m,-1);
				Insert(i,-1);
				ans=max(ans,mx[1]+(int)ve[i].size());
				Insert(i,1);
			}
			return ans;
		}
};