Robot Queries
Contest: Educational Codeforces Round 159 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search, data structures, dp, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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:

Example input:
8 3
RDLLUURU
-1 2 1 7
0 0 3 4
0 1 7 8

Example output:
YES
YES
NO

Example input:
4 2
RLDU
0 0 2 2
-1 -1 2 3

Example output:
YES
NO

Editorial:
Let's divide the path of the robot into three parts:
1. points before the $$$l$$$-th operation;
2. points from the $$$l$$$-th to the $$$r$$$-th operations;
3. points after the $$$r$$$-th operation;
The first and the third parts are pretty simple to check because the reverse of the substring $$$(l, r)$$$ does not affect them. So we can precompute a dictionary $$$mp_{x, y}$$$ that stores all indices of operations in the initial sequence $$$s$$$ after which the robot stands at the point $$$(x, y)$$$. Then point $$$(x, y)$$$ lies on the first part if $$$mp_{x, y}$$$ contains at least one index among indices from $$$0$$$ to $$$l-1$$$. Similarly, for the third part, but we have to check indices from $$$r$$$ to $$$n$$$.
It remains to understand how the second part works. Reversing of the order of commands from $$$l$$$ to $$$r$$$ means that the robot first performs all commands from $$$1$$$ to $$$l-1$$$ in the original string, then the command $$$s_r$$$, then $$$s_{r-1}$$$, and so on, until the command $$$s_l$$$. So, it means that the points that the robot visits can be represented as follows: for an integer $$$k$$$ such that $$$l \le k \le r$$$, perform all commands from $$$1$$$ to $$$r$$$, except for the commands from $$$l$$$ to $$$k$$$.
Let $$$pos_i$$$ be the point where the robot stands after the $$$i$$$-th operation, and $$$\Delta_{i, j}$$$ be the total movement using operations from $$$i$$$ to $$$j$$$ (note that $$$\Delta_{i, j} = pos_j - pos_{i-1}$$$). Then we have to check whether there is such $$$i$$$ that $$$l \le i \le r$$$ and $$$pos_{l-1} + \Delta_{i, r} = (x, y)$$$. Using the aforementioned equality for $$$\Delta$$$, we can rewrite this as $$$pos_{l-1} + pos_r - pos_i = (x, y)$$$. As a result, our task is to check whether there is such $$$i$$$ that $$$l \le i \le r$$$ and $$$pos_i = pos_{l-1} + pos_r - (x, y)$$$. And we already know how to check that, using the dictionary $$$mp$$$ (you will need some sort of binary search or a function similar to lower_bound to find whether there is a moment from $$$l$$$ to $$$r$$$ when a point is visited).
If the point belongs to at least one of the parts of the path, then the answer is YES, otherwise the answer is NO.