无穷大的二位网格平面上, $(0, 0)$ 处有一个障碍物. 现在有一个由 R, L, U, D 组成的长度为 $n$ 的操作序列和一个机器人. 操作序列表示控制机器人如何走(上下左右), 如果机器人的下一步是障碍物(即原点), 那么他不行动. 现在有 $Q$ 次询问, 每次询问给出机器人的起点, 问终点. 保证机器人不在 $(0, 0)$.
$1 \le n, q \le 3 \cdot 10^5$
jyz nb!
不要被"一个“给误导了, 把所有询问都放在图上, 然后同时开始执行操作, 想象一下, 是不是有种"背景在动"的感觉? 没错, 这就是 “相对运动”. 与其操作 $Q$ 个机器人, 不如反向操作一个障碍物. 假设在障碍物移动的过程中, 没有碰到任何机器人, 那么障碍物移动的轨迹反一下, 就是所有机器人移动的轨迹了. 障碍物移动的轨迹可以通过二位向量前缀和求得. 统计答案每个机器人起点对它做差即可. 于是, 对于障碍物移动过程中碰到的机器人, 我们想办法改变机器人的起点, 使得其终点不变, 但不再碰见障碍物. 这是好办的, 因为障碍物碰见机器人了的话, 就证明机器人在这个时候会去撞障碍物(相对运动), 那么让机器人"后退"一步, 再执行这个操作, 后续操作是一模一样的. 所以做法就是, 相对运动移动障碍物, 碰到机器人就"推"一下. 需要注意的是, 障碍物移动一下最多推 $n$ 个机器人, 但是这些机器人在后续操作中就等价了, 所以只用搞一个代表出来就行, 用并查集合并一下即可.
复杂度 $O(\alpha n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
int fa[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool uni(int x, int y) {
if (find(x) == find(y))
return false;
fa[find(x)] = find(y);
return true;
}
struct Vec {
int x, y;
Vec operator + (const Vec &B) const { return Vec{x + B.x, y + B.y}; }
Vec operator - (const Vec &B) const { return Vec{x - B.x, y - B.y}; }
bool operator == (const Vec &B) const {
return x == B.x && y == B.y;
}
bool operator < (const Vec &V) const {
return x == V.x ? y < V.y : x < V.x;
}
} d[256], ans[MAXN];
map<Vec, int> mp;
int n, q;
char str[MAXN];
int main() {
d['U'] = {0, 1};
d['D'] = {0, -1};
d['L'] = {-1, 0};
d['R'] = {1, 0};
scanf("%d%s%d", &n, str, &q);
init(q);
for (int i = 1; i <= q; i++) {
Vec cur;
scanf("%d%d", &cur.x, &cur.y);
if (mp[cur])
uni(i, mp[cur]);
else
mp[cur] = i;
}
Vec cur = {0, 0};
for (int i = 0; str[i]; i++) {
cur = cur - d[str[i]];
if (mp[cur]) {
Vec nxt = cur - d[str[i]];
if (mp[nxt])
uni(mp[cur], mp[nxt]);
else
mp[nxt] = mp[cur];
mp.erase(cur);
}
}
for (auto [v, i] : mp)
ans[i] = v - cur;
for (int i = 1; i <= q; i++)
printf("%d %d\n", ans[find(i)].x, ans[find(i)].y);
return 0;
}
|