题目传送门
前置知识——向量的加减
\((x_1,y_1) \pm (x_2,y_2) = (x_1\pm x_2,y_1\pm y_2)\)。
满足交换律和结合律。
题目大意
有一个在 \((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
#include <bits/stdc++.h>#pragma GCC optimize("Ofast")#define int long longusing 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] = {a[i - 1].first, a[i - 1].second + 1};} else if (ch == 'D') {a[i] = {a[i - 1].first, a[i - 1].second - 1};} else if (ch == 'L') {a[i] = {a[i - 1].first - 1, a[i - 1].second};} else {a[i] = {a[i - 1].first + 1, a[i - 1].second};}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;
}