HT-014 Div3 扫雷 题解 [ 绿 ] [ 二维差分 ]

分析

观察到是曼哈顿距离 \(\le r\) 的范围可以扫到，联想到如下图形：

左边是 \(r=1\) 可以扫到的范围，右边是 \(r=2\) 可以扫到的范围。

于是，我们只要对这样的图形在 \(1000*1000\) 的格子里差分一下就好了 。

但这样的复杂度是 \(O(nm)\) 的，会死的很惨。

优化

不难发现这个图形是一个旋转过 \(45°\) 的正方形，所以我们先把他转回来。

归纳法可以得到原先为 \((x,y)\) 的点会变换为 \((n+x-y,x+y-1)\) 。
严格证明有点忘了，记得好像是用一次函数证的。

于是我们就把一个斜着的图形变正了。

接下来就是把这个正方形的四个顶点算出来并且变换一下，套一个二维差分的板子，很简单。

时间为 \(O(m)\) ，常数有点大。

另外，为了不特判边界情况，可以直接开 \(4000*4000\) 的数组，把变换后的点横纵坐标都加一个 \(1000\) ，就不用处理下标为负数的情况。出题人比较好心，给了 \(2000ms\) 和 \(1024Mib\) 。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
int n,m,f[5005][5005],q;
pi change(pi ori)
{
	int x=ori.first,y=ori.second;
	return {n+x-y+1100,x+y-1+1100};
}
bool check(pi t)
{
	int x=t.first,y=t.second;
	return (x>=1&&x<=2*n-1&&y>=1&&y<=2*n-1);
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int x,y,r;
		cin>>x>>y>>r;
		pi zs=change({x-r,y});
		pi zx=change({x,y-r});
		pi ys=change({x,y+r});
		pi yx=change({x+r,y});
		f[zs.first][zs.second]++;
		f[zx.first+1][zx.second]--;
		f[ys.first][ys.second+1]--;
		f[yx.first+1][yx.second+1]++;
	}
	for(int i=1;i<=5000;i++)
	{
		for(int j=1;j<=5000;j++)
		{
			f[i][j]=f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];
		}
	}
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		pi now=change({x,y});
		cout<<f[now.first][now.second]<<endl;
	}
	return 0;
}