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;
}