题意
有一个无限的 $2$ 维网格。一开始，机器人站在 $(0, 0)$ 点。机器人可以执行四条指令：
- U：从点 $(x, y)$ 移动到 $(x, y + 1)$ ；
- D：从点 $(x, y)$ 移动到 $(x, y - 1)$ ；
- L：从点 $(x, y)$ 移动到 $(x - 1, y)$ ；
- R：从点 $(x, y)$ 移动到 $(x + 1, y)$ 。
给你一串长度为 $n$ 的命令 $s$ 。您的任务是回答 $q$ 独立的查询：给定四个整数 $x$ 、 $y$ 、 $l$ 和 $r$ ；判断机器人在执行命令序列 $s$ 时是否访问了点 $(x, y)$ ，但 $l$ 到 $r$ 的子串是相反的（即机器人执行命令的顺序是 $s_1 s_2 s_3 \dots s_{l-1} s_r s_{r-1} s_{r-2} \dots s_l s_{r+1} s_{r+2} \dots s_n$ ）。
题解
每次查询，机器人的路径分为三个部分：
- $[1, l - 1]$；
- $[l, r - 1]$；
- $[r, n]$。
我们可以开个map，记录下每个点分别在第几步之后到达，于是第一三部分就很容易做掉了。
对于第二部分，我们设 $a_i $ 为原操作序列走完 $i$ 步后的位置，设翻转后中第 $k$ 步走完后到达 $(x, y)$（$l \le k < r$），则有 $a_r - a_k$ 为走完 $l - 1$ 步后产生的偏移量（第 $r$ 步走到第 $k$ 步和第 $k$ 步走到 $r$ 步产生的总偏移量是相同的），所以 $a_l + a_r - a_k = (x, y)$。移项得到 $a_l + a_r - (x, y) = a_k$，于是我们可以在map里找到点 $a_l + a_r - (x, y)$，然后看有无 $k$ 使得第 $k$ 步走完后到达点 $a_l + a_r - (x, y)$ 且满足 $l \le k < r$。
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int n, q;
pair <int, int> a[200010];
string s;
map <pair <int, int>, vector <int>> p;
bool find (pair <int, int> x, int l, int r) {
if (p.find (x) == p.end ()) return false;
auto id = lower_bound (p.begin (), p.end (), l);
return (id != p.end () && *id <= r);
} //查询 a[l~r]中有无点x
int main () {
ios::sync_with_stdio (false);
cin.tie (0);
cin >> n >> q;
cin >> s; s = ' ' + s;
p[{0, 0}].push_back (0);
a[0] = {0, 0};
for (int x = 0, y = 0, i = 1; i <= n; i++) {
x += (s[i] == 'R') - (s[i] == 'L');
y += (s[i] == 'U') - (s[i] == 'D');
a[i] = {x, y};
p[{x, y}].push_back (i);
}
while (q--) {
int x, y, l, r;
cin >> x >> y >> l >> r;
bool flag = false;
flag |= find ({x, y}, 0, l - 1);
flag |= find ({x, y}, r, n);
flag |= find ({a[r].first + a[l - 1].first - x, a[r].second + a[l - 1].second - y}, l, r - 1);
cout << (flag ? "YES" : "NO") << '\n';
}
return 0;
}