Educational Codeforces Round 132 (Rated for Div. 2) D. Rorororobot

D. Rorororobot

题意

有一个n行m列的网格，每一列上$1$~ $a_i$的位置上是障碍物，机器人可以连续走k步，给你一个起点和终点，问你能否在不路过障碍物和不超过格子的情况下从起点走到终点。

考点

数据结构，分类讨论

思路

首先，我们需要用数据结构维护出从起点列到终点列的最大值，我们设它为$x$。
其次我们分情况讨论：

1.假如起和终点在同一列上，则只需要判断横坐标之差是不是k的倍数即可。

2.如果不在同一列，要保证两点横坐标的差和纵坐标的差的绝对值都是k的倍数

3.如果横坐标较大的那个点的高度比$x$低，要保证能走到x上面但不越界的空白区域（如下图的棕色区域），在此区域走到另一个点的纵坐标那。

代码

const int N = 200010;
struct Node{
    
	int maxn;
}seg[N * 4];
 
int a[N];
int n, m;
void pushup(int u){
    
	seg[u].maxn = max(seg[u << 1].maxn, seg[u << 1 | 1].maxn);
}
void build(int u, int l, int r){
    
	if(l == r){
    
		seg[u].maxn = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}
int query(int u, int l, int r, int ql, int qr){
    
	if(l == ql && r == qr) return seg[u].maxn;
	int mid = l + r >> 1;
	if(qr <= mid) return query(u << 1, l, mid, ql, qr);
	else if(ql > mid) return query(u << 1 | 1, mid + 1, r, ql, qr);
	else return max(query(u << 1, l, mid, ql, mid), query(u << 1 | 1,mid + 1, r, mid + 1, qr));
}
int main(){
    
	scanf("%d %d",&n, &m);
	for(int i = 1; i <= m; i ++ ){
    
		scanf("%d",&a[i]);
	}
	int q;
	scanf("%d",&q);
	build(1, 1, m);
	while(q -- ){
    
		int sx, sy, ex, ey, k;
		scanf("%d %d %d %d %d",&sx, &sy, &ex, &ey, &k);
		int miny = min(ey, sy), maxy = max(ey, sy);
		int minx = min(ex, sx), maxx = max(ex, sx);
		int a = abs(ex - sx), b = abs(ey - sy), x = query(1, 1, m, miny, maxy);
		//在同一列
		if(!b){
    
			if(a % k) puts("No");
			else puts("Yes");
			continue;
		}
		if(a % k || b % k){
    
			puts("No");
			continue;
		}
		if(x < maxx){
    
			puts("Yes");
			continue;
		}
		int mod = (x - maxx) % k;
		if(n - x + mod >= k) puts("Yes");
		else puts("No");
 
	}
	return 0;
}