RainbowDash 的 Robot

H RainbowDash 的 Robot - 第七届校赛正式赛 —— 补题

题目大意：

给一个 $n\ast m$ 的二维网格，在第 $i$ 列中，前 $a_i$ 单元格被阻断，无法通行，即 $[1,a_i]$ 。

一个机器人正在这个网格内移动，你可以向他发送指令，使得其向 上下左右 移动，但是这个机器人是由缺陷的，每条指令会执行 $k$ 次，因此，机器人每次移动 $k$ 个单元格，如果机器人试图移动到受阻的单元格或网格外，就会爆炸。

有 $q$ 次询问，每次询问都有一个起始单元格 $sx,sy$ ，一个终点单元格 $fx,fy$ 和一个值 $k$ 。

若机器人执行任意次命令，能否从起点单元到达终点单元

$1<=n<=10^9,1<=m<=2\ast 10^5$

$0<=a_i<=n$

$1<=q<=2\ast 10^5$

$1<=k<=10^9$

保证起点坐标和终点坐标有效

思路：

优先考虑机器人从起点坐标走到终点坐标需要满足的条件，

$sx$ 到 $fx$ 之间距离必须是 $k$ 的倍数，$sy$ 到 $fy$ 之间距离必须是 $k$ 的倍数

if( llabs(sx-fx)%k!=0 || llabs(sy-fy) ){
	cout<<"No\n";
	continue;
}

满足以上条件之后，考虑从 $sy$ 到达 $fy$ ，需要满足之间没有受阻的网格，所以贪心的想，优先走到该列最下面，再往左右走，考虑从第 $sy$ 到 $fy$ 之间最大的受阻网格为多少即可，数据范围较大，维护区间最值可选用线段树 。

int len=sx+(n-sx)/k*k;
auto x=query(1,1,m,min(sy,fy),max(sy,fy));
if(x.mx>=len){
	cout<<"No\n";
}else{
	cout<<"Yes\n";
}

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()

const int mod = 1e9 + 7;
const int N = 1e6 + 10;

int a[N];
struct node
{
	int lz;
	int mx;
}tr[N*4];

node push_up(node L,node R)
{
	node res={0,0};
	res.mx=max(L.mx,R.mx);
	return res; 
}

void build(int p,int l,int r)
{
	if(l==r){
		tr[p].mx=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tr[p]=push_up(tr[p*2],tr[p*2+1]);
}

node query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R){
		return tr[p];
	}
	node res={0,0};
	int mid=l+r>>1;
	if(L<=mid) res=push_up(res,query(p*2,l,mid,L,R));
	if(R>mid) res=push_up(res,query(p*2+1,mid+1,r,L,R));
	return res;
}

void solve() {
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}	
	build(1,1,m);
	int q;cin>>q;
	while(q--){
		int sx,sy,fx,fy,k;cin>>sx>>sy>>fx>>fy>>k;
		if(llabs(sx-fx)%k!=0||llabs(sy-fy)%k!=0){
			cout<<"No\n";
			continue;
		}
		auto x=query(1,1,m,min(sy,fy),max(sy,fy));
		int len=sx+(n-sx)/k*k;
//		cout<<x.mx<<" "<<len<<'\n';
		if(x.mx>=len){
			cout<<"No\n";
		}else{
			cout<<"Yes\n";
		}
	}
}

signed main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}