Robot Queries (Codeforces 1902D)
Tags: Implement, binary search

There is an infinite $$$2$$$-dimensional grid. Initially, a robot stands in the point $$$(0, 0)$$$. The robot can execute four commands:  U — move from point $$$(x, y)$$$ to $$$(x, y + 1)$$$;  D — move from point $$$(x, y)$$$ to $$$(x, y - 1)$$$;  L — move from point $$$(x, y)$$$ to $$$(x - 1, y)$$$;  R — move from point $$$(x, y)$$$ to $$$(x + 1, y)$$$. You are given a sequence of commands $$$s$$$ of length $$$n$$$. Your task is to answer $$$q$$$ independent queries: given four integers $$$x$$$, $$$y$$$, $$$l$$$ and $$$r$$$; determine whether the robot visits the point $$$(x, y)$$$, while executing a sequence $$$s$$$, but the substring from $$$l$$$ to $$$r$$$ is reversed (i. e. the robot performs commands in order $$$s_1 s_2 s_3 \dots s_{l-1} s_r s_{r-1} s_{r-2} \dots s_l s_{r+1} s_{r+2} \dots s_n$$$).

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the length of the command sequence and the number of queries, respectively.The second line contains a string $$$s$$$ of length $$$n$$$, consisting of characters U, D, L and/or R.Then $$$q$$$ lines follow, the $$$i$$$-th of them contains four integers $$$x_i$$$, $$$y_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$-n \le x_i, y_i \le n$$$; $$$1 \le l \le r \le n$$$) describing the $$$i$$$-th query.

Output: For each query, print YES if the robot visits the point $$$(x, y)$$$, while executing a sequence $$$s$$$, but the substring from $$$l$$$ to $$$r$$$ is reversed; otherwise print NO.

Note: In the first query of the first sample, the path of the robot looks as follows:   In the second query of the first sample, the path of the robot looks as follows:   In the third query of the first sample, the path of the robot looks as follows:   

Sample Inputs:
8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8

4 2
RLDU
0 0 2 2
-1 -1 2 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

Sample Outputs:
YES
YES
NO

YES
NO

YES
YES
YES
NO
YES
YES

Solution (Python):
import bisect
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_search(sorted_lst, low, high):
    left = bisect.bisect_left(sorted_lst, low)
    return left != len(sorted_lst) and sorted_lst[left] <= high
(n, q) = map(int, input().split())
S = input().decode().rstrip()
DIR = {'U': (0, 1), 'D': (0, -1), 'L': (-1, 0), 'R': (1, 0)}
pts = {(0, 0): [0]}
lst = [(0, 0)]
for i in range(n):
    (dx, dy) = DIR[S[i]]
    pt = (lst[-1][0] + dx, lst[-1][1] + dy)
    if pt not in pts:
        pts[pt] = [i + 1]
    else:
        pts[pt].append(i + 1)
    lst.append(pt)
ans = []
for _ in range(q):
    (x, y, l, r) = map(int, input().split())
    l -= 1
    pt = (x, y)
    found = False
    if pt in pts:
        if pts[pt][0] <= l or pts[pt][-1] >= r:
            found = True
    if not found:
        (Lx, Ly) = lst[l]
        (Rx, Ry) = lst[r]
        pt_2 = (Lx + Rx - x, Ly + Ry - y)
        if pt_2 in pts:
            found = binary_search(pts[pt_2], l + 1, r - 1)
    ans.append('YES' if found else 'NO')
sys.stdout.write('\n'.join(ans))

Solution (Python):
import io
import os
from collections import defaultdict
from bisect import bisect_left
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
S = '_' + input().rstrip().decode()
X = [0] * (n + 1)
Y = [0] * (n + 1)
traversals = defaultdict(list)
for (i, d) in enumerate(S):
    if d == 'U':
        Y[i] = Y[i - 1] + 1
        X[i] = X[i - 1]
    elif d == 'D':
        Y[i] = Y[i - 1] - 1
        X[i] = X[i - 1]
    elif d == 'L':
        X[i] = X[i - 1] - 1
        Y[i] = Y[i - 1]
    elif d == 'R':
        X[i] = X[i - 1] + 1
        Y[i] = Y[i - 1]
    traversals[X[i], Y[i]].append(i)
for _ in range(q):
    (x, y, l, r) = map(int, input().split())
    if (x, y) in traversals:
        tvs = traversals[x, y]
        if tvs[0] < l or tvs[-1] >= r:
            print('YES')
            continue
    (new_x, new_y) = (X[r] + X[l - 1] - x, Y[r] + Y[l - 1] - y)
    if (new_x, new_y) in traversals:
        tvs = traversals[new_x, new_y]
        idx = bisect_left(tvs, l)
        if idx < len(tvs) and tvs[idx] < r:
            print('YES')
            continue
    print('NO')

Solution (Python):
import bisect
import sys
from os import path
s_map = {}
max_size = 200002
X = [0] * max_size
Y = [0] * max_size

def ask(x, y, l, r):
    if (x, y) not in s_map:
        return False
    pos = s_map[x, y]
    idx = bisect.bisect_left(pos, l)
    if idx >= len(pos):
        return False
    return pos[idx] <= r

def main():
    if path.exists('in.txt'):
        sys.stdin = open('in.txt', 'r')
    input = sys.stdin.readline
    (n, q) = map(int, input().split())
    s = input().strip()
    for i in range(1, n + 1):
        si = s[i - 1]
        X[i] = X[i - 1]
        Y[i] = Y[i - 1]
        if si == 'U':
            Y[i] += 1
        elif si == 'D':
            Y[i] -= 1
        elif si == 'L':
            X[i] -= 1
        else:
            X[i] += 1
    for i in range(0, n + 1):
        pair = (X[i], Y[i])
        if pair in s_map:
            s_map[pair].append(i)
        else:
            s_map[pair] = [i]
    for _ in range(q):
        (x, y, l, r) = map(int, input().split())
        if ask(x, y, 0, l - 1):
            print('YES')
        elif ask(x, y, r, n):
            print('YES')
        elif ask(X[l - 1] + X[r] - x, Y[l - 1] + Y[r] - y, l, r):
            print('YES')
        else:
            print('NO')
main()