CF1902D Robot Queries 题解

题意：有一个二维平面直角坐标系，给定一串向某个方向移动 \(1\) 个单位的操作。

有 \(q\) 个询问，对于每个询问给定 \(x,y,l,r\)，问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作，是否会经过 \((x,y)\)。

ds 题。先预处理出 \(sx_i,sy_i\) 表示执行完操作 \(i\) 后的位置，如果在 \([l,r]\) 区间外已经经过 \((x,y)\) 了，那么最终也一定会经过。再考虑 \([l,r]\) 区间内，我们会发现，如果正序执行操作时会到达 \((nx,ny)\) 的话，那么倒序执行操作时一定会经过 \((sx_{l-1}+sx_r-nx,sy_{l-1}+sy_r-ny)\)。所以只需要查询区间内是否存在一个坐标即可。可以线段树，这里用的离线 vector + map。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> pii;
map <pii,int> f,s,mp;
const int MAXN = 2e5 + 10;
int n,q,x,y,l,r,sx[MAXN],sy[MAXN],ans[MAXN];
struct Node{int i,l,x,y;};
vector <Node> a[MAXN];
char c[MAXN];
signed main()
{
	cin >> n >> q >> (c + 1);
	for(int i = 1;i <= n;i++)
	{
		sx[i] = sx[i - 1],sy[i] = sy[i - 1];
		if(c[i] == 'R') sx[i]++;
		if(c[i] == 'L') sx[i]--;
		if(c[i] == 'U') sy[i]++;
		if(c[i] == 'D') sy[i]--;
	}
	for(int i = 0;i <= n;i++) f[make_pair(sx[i],sy[i])] = i;
	for(int i = n;i >= 0;i--) s[make_pair(sx[i],sy[i])] = i;
	for(int i = 1;i <= q;i++)
	{
		cin >> x >> y >> l >> r;
		if(f.count(make_pair(x,y)) && f[make_pair(x,y)] >= r) ans[i] = 1;
		if(s.count(make_pair(x,y)) && s[make_pair(x,y)] < l) ans[i] = 1;
		a[r].push_back({i,l,sx[l - 1] + sx[r] - x,sy[l - 1] + sy[r] - y});
	}
	for(int i = 0;i <= n;i++)
	{
		mp[make_pair(sx[i],sy[i])] = i;
		for(int j = 0;j < a[i].size();j++) 
			ans[a[i][j].i] |= mp[make_pair(a[i][j].x,a[i][j].y)] >= a[i][j].l;
	}
	for(int i = 1;i <= q;i++) cout << (ans[i] ? "YES" : "NO") << endl;
	return 0;
}