https://codeforces.com/contest/1902/problem/D
题目大意
给出某 LRUD 组成的 $n \ (\le 2 \times 10^5)$ 的操作序列 $S$ 以及 $q \ (\le 2 \times 10^5)$ 个询问。询问之间彼此独立。每次问，将原始操作序列 $[l, r]$ 的这一段反转后，整个操作序列以 $(0, 0)$ 为起点会不会通过 $(x, y)$。（$S$ 翻转 $[l, r]$ 之后的序列为 $s_0 s_1 s_2 \cdots s_{l - 1} s_r s_{r - 1} s_{r - 2} \cdots s_{l + 1} s_l s_{r + 1} s_{r + 2} \cdots s_n$。）
简要题解
观察：
执行一串操作之后，只与每种操作次数有关，与顺序无关。我们假定 $pos[i]$ 表示执行了 $i$ 次操作之后的位置，则，$[l, r]$ 翻转不会影响，$0 \sim i-1$ 和 $r \sim n$ 的 $pos$ 的值。于是我们可以用前后缀分别处理每个询问，在翻转区间外是否已经经过了点。
对于翻转的区间，我们注意到，这里翻转后的路径和翻转前有一定的对称关系。假设要求的点为 $p$，其位于翻转后的序列在$l - 1$ 次操作之后又执行了 $k$ 次操作的位置，假定这 $k$ 次操作造成的相对于 $pos[l - 1]$ 的偏移向量为 $v = p - pos[l - 1]$ 则显然，在原序列里，这一段操作发生在结尾，即由 $p' = pos[r - k]$ 偏移 $v$ 之后到达 $pos[r]$。可以列出等式 $v = p - pos[l - 1] = pos[r] - p'$。
当然这里我们不知道 $k$ 的值，我们只需要找 $r$ 之前，最后出现的 $p'$ 对应的 pos 中的下标，如果这个下标是晚于 $l$ 的，则说明找到了。
复杂度
$T$：$O(n \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
typedef array<int, 4> A4;
map<char, int> dx, dy;
void init() {
dx['U'] = 0;
dx['D'] = 0;
dx['L'] = -1;
dx['R'] = 1;
dy['U'] = 1;
dy['D'] = -1;
dy['L'] = 0;
dy['R'] = 0;
}
void solve() {
int n, q; cin >> n >> q;
string op; cin >> op;
int x, y, l, r;
vector<vector<A4>> qs(n + 1), qs2(n + 1);
for (int i = 0; i < q; i++) {
cin >> x >> y >> l >> r;
qs[l].push_back({x, y, r, i});
qs2[r].push_back({x, y, l, i});
}
vector<int> px, py;
px.push_back(0);
py.push_back(0);
for (int i = 0; i < n; i++) {
px.push_back(px.back() + dx[op[i]]);
py.push_back(py.back() + dy[op[i]]);
}
// for (int i : px) cerr << i << ' ';
// cerr << endl;
// for (int i : py) cerr << i << ' ';
// cerr << endl;
vector<int> ans(q);
set<PII> se;
for (int i = 0; i <= n; i++) {
for (auto&& [x, y, r, id] : qs[i]) {
if (se.count({x, y})) {
ans[id] = 1;
}
}
se.insert({px[i], py[i]});
}
se.clear();
for (int i = n; i >= 0; i--) {
se.insert({px[i], py[i]});
for (auto&& [x, y, l, id] : qs2[i]) {
if (se.count({x, y})) {
ans[id] = 1;
}
}
}
// 0 1 2 3 4 5
// [ ] [1, 4] -> 1 3
map<PII, int> lst;
for (int i = 0; i <= n; i++) {
for (auto&& [x, y, l, id] : qs2[i]) {
int nx = px[i] + px[l - 1] - x, ny = py[i] + py[l - 1] - y;
// cerr << x << ' ' << y << ' ' << l << ' ' << i << ' ';
// cerr << px[l - 1] << ' ' << px[r] << ' ' << py[l - 1] << ' ' << py[i] << ' ';
// cerr << nx << ' ' << ny << endl;
if (auto it = lst.find({nx, ny}); it != lst.end()) {
if (it->second >= l) {
ans[id] = 1;
}
}
}
lst[{px[i], py[i]}] = i;
}
for (int i : ans) {
cout << (i ? "YES" : "NO") << '\n';
}
}
int main() {
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Insert and Equalize - Educational Codeforces Round 159 (Rated for Div. 2)