D. Robot Queries
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\)).
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.
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.
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: