题解：CF1902D Robot Queries
Charllote_
·
·
题解
题目传送门
更好的阅读体验
前置知识——向量的加减
满足交换律和结合律。
## 题目大意
有一个在 $(0,0)$ 的点。现在给出 $n$ 个操作序列 ${f}$，每个指令形如 $(x, y) \gets \left\{\begin{matrix}(x \pm 1, y) \\(x, y \pm 1)\end{matrix}\right.$。现在又有 $q$ 个互相独立的询问，每个询问为反转 $a_l\sim a_r$，给出 $(x, y)$ 是否被点经过。
## 思路
一、操作序列等价于一组向量：$\{(\pm 1,0),(0,\pm 1)\}$。对于每一个询问，等价于询问反转后的操作序列 ${b}$ 是否有 $(x, y) = \sum_{i - 1}^n b_i$。设 $a_i = \sum_{j=1}^i f_j$。
二、由向量加法满足交换律容易得到 $\forall p\in[1,l)\cup[r,n], a_p \text{不变}$。所以其中一种合法情况为 $a_i$ 等于 $(x, y)$ 且 $\forall p\in[1,l)\cup[r,n]$。
三、由找规律可得，反转一段区间等价于将这一段的路径 $\{b\}$ 旋转 $180^{\circ}$ 再把 ${b}$ 的起点平移到 $a_{l-1}$。所以另外一种合法情况为 $a_{l - 1} + a_r - (x, y) = b_p$ 且 $\forall p \in [l, r)$。
## 实现
使用一个 `map<PII, vector<int>> mp` 维护 $b = a_i$ 的 $i$。对于第一种情况，直接判断 `mp[{x, y}]` 中是否有 $p\in[1,l)\cup[r,n]$ 即可。对于第二种情况，判断 `mp[add(add(re(p), a[l - 1]), a[r])]` 中是否有 $p\in[l,r)$ 即可。判断可以使用二分。
## code
```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
const int N = 2e5 + 5;
using PII = pair<int, int>;
int n, q, x, y, l, r;
PII a[N];
map<PII, vector<int>> mp;
PII add(PII x, PII y) {
return {x.first + y.first, x.second + y.second};
}
PII re(PII x) {
return {-x.first, -x.second};
}
bool check(vector<int> &v, int l, int r) {
auto it = lower_bound(v.begin(), v.end(), l);
if (it == v.end()) return false;
return *it <= r;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
mp[{0, 0}].push_back(0);
for (int i = 1; i <= n; i ++ ) {
char ch; cin >> ch;
if (ch =='U') { a[i] = add(a[i - 1], {0, 1}); }
else if (ch =='D') {a[i] = add(a[i - 1], {0, -1});}
else if (ch =='L') {a[i] = add(a[i - 1], {-1, 0});}
else if (ch =='R') {a[i] = add(a[i - 1], {1, 0});}
mp[a[i]].push_back(i);
}
while (q -- ) {
cin >> x >> y >> l >> r;
PII p = {x, y};
if (mp.count(p) && (check(mp[p], 0, l - 1) || check(mp[p], r, n))) {
cout << "YES\n";
continue;
}
PII finded = add(add(re(p), a[l - 1]), a[r]);
if (mp.count(finded) && check(mp[finded], l, r - 1)) {
cout << "YES\n";
continue;
}
cout << "NO\n";
}
return 0;
}
```