题目描述

难度分:$1900$

输入$n(1 \leq n \leq 2 \times 10^5)$，$q(1 \leq q \leq 2 \times 10^5)$和长为 $n$的字符串$s$，只包含UDLR。

一开始，你在平面直角坐标系的原点$(0,0)$，你需要从左到右执行$s$上的操作，UDLR分别表示向上/下/左/右移动一个单位。

然后输入$q$个询问，每个询问输入$x$、$y(-n \leq x,y \leq n)$、$l$、 $r(1 \leq l \leq r \leq n)$。

你需要把原串$s$的下标从$l$到$r$这一段$reverse$。（下标从$1$开始）然后依旧从 $(0,0)$出发，从左到右执行$s$上的操作，判断路径是否包含$(x,y)$。输出YES或NO。

注意询问是互相独立的，每次询问修改的都是原串$s$。

输入样例$1$

8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8

输出样例$1$

YES
YES
NO

输入样例$2$

4 2
RLDU
0 0 2 2
-1 -1 2 3

输出样例$2$

YES
NO

输入样例$3$

10 6
DLUDLRULLD
-1 0 1 10
-1 -2 2 5
-4 -2 6 10
-1 0 3 9
0 1 4 7
-3 -1 5 8

输出样例$3$

YES
YES
YES
NO
YES
YES

算法

前缀和+二分查找

构建一个二元组数组$idx2pos$，$idx2pos[i]$表示执行完指令$i$时的横纵坐标。构建一个哈希映射$pos2idx$，$pos2idx[(x,y)]$表示处于$(x,y)$位置时的指令编号列表。

分析一下可以发现，对于某条询问$(x,y,l,r)$，如果$(x,y)$最早出现的指令编号$\lt l$，或$\gt r$，反转子串$[l,r]$就没有任何影响，直接输出YES。否则$(x,y)$出现时就应该在子串$[l,r]$内部，如果要求在执行这一段指令时经过了$(x,y)$这个位置，假设是指令$i \in [l,r]$时经过的，反转$[l,r]$之后就相当于先执行指令$[1,l-1]$，再反着执行指令$[i,r]$。而执行某一段区间的指令时对$x$和$y$的增量$dx$和$dy$并不会因为反转了指令序列而发生改变，因此根据前缀和的思想，执行$[i,r]$指令带来的两个维度的增量分别为

$dx=idx2pos[r].x-idx2pos[i-1].x$
$dy=idx2pos[r].y-idx2pos[i-1].y$

而我们要求

$idx2pos[l-1].x+dx=x$
$idx2pos[l-1].y+dy=y$

所以

$nx=idx2pos[i-1].x=idx2pos[l-1].x+idx2pos[r].x-x$
$ny=idx2pos[i-1].y=idx2pos[l-1].y+idx2pos[r].y-y$。

最后二分查找$pos2idx[(nx,ny)]$中大于等于$l-1$的第一个指令是不是$\lt r$（因为$i \in [l,r]$，所以$i-1 \in [l-1,r)$），是就说明反转完$[l,r]$会经过$(x,y)$，否则不经过。

复杂度分析

时间复杂度

实现的时候没有重现哈希函数，$pos2idx$使用的有序表，但这里还是按理论的时间复杂度来分析。预处理得到$idx2pos$和$pos2idx$只需要遍历一遍字符串$s$，时间复杂度是线性的，为$O(n)$。接下来在线处理每条询问，在最差情况下需要对每条询问都进行时间复杂度为$O(log_2n)$的二分查找，因此时间复杂度为$O(qlog_2n)$。

综上，整个算法的时间复杂度为$O(n+qlog_2n)$。

空间复杂度

除了输入的字符串$s$，使用了映射$pos2idx$，其中最多存$O(n)$级别的指令。还使用了$idx2pos$数组，它记录了原本的$n$条指令执行完时的位置，也是$O(n)$的。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, q;
char s[N];

int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", s + 1);
    vector<array<int, 2>> idx2pos(n + 1);
    map<array<int, 2>, vector<int>> pos2idx;
    int x = 0, y = 0;
    pos2idx[{x, y}].push_back(0);
    idx2pos[0] = {x, y};
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'L') x--;
        else if(s[i] == 'R') x++;
        else if(s[i] == 'U') y++;
        else y--;
        pos2idx[{x, y}].push_back(i);
        idx2pos[i] = {x, y};
    }
    for(int i = 1; i <= q; i++) {
        int x, y, l, r;
        scanf("%d%d%d%d", &x, &y, &l, &r);
        if(pos2idx.count({x, y}) && pos2idx[{x, y}][0] < l) {
            puts("YES");
            continue;
        }
        if(pos2idx.count({x, y}) && pos2idx[{x, y}].back() > r) {
            puts("YES");
            continue;
        }
        int nx = idx2pos[l - 1][0] + idx2pos[r][0] - x, ny = idx2pos[l - 1][1] + idx2pos[r][1] - y;
        if(pos2idx.count({nx, ny})) {
            auto& v = pos2idx[{nx, ny}];
            auto it = lower_bound(v.begin(), v.end(), l - 1);
            if(it != v.end() && *it <= r) {
                puts("YES");
            }else {
                puts("NO");
            }
        }else {
            puts("NO");
        }
    }
    return 0;
}