Python || Interval Tree || Time O(m log**2 m)
First, simulate all the moves once, assuming the robot starts at the top left. Then, create interval trees for the row and column positions. The interval tree n
First, simulate all the moves once, assuming the robot starts at the top left. Then, create interval trees for the row and column positions. The interval tree nodes are in the form of `(min_val, max_val)`.\nWith this, we can query the interval tree to find the ranges of rows and column movements of the robot for any subarray of commands.\nFinally, for each element of the answer, we use binary search to find the last command which does not move the robot outside of the grid.\n\n```\ndef f(a, b):\n    return (min(a[0], b[0]), max(a[1], b[1]))\n\n\nclass IntervalTree:\n    def __init__(self, t):\n        pow2 = 1\n        n = len(t)\n        while pow2 < n:\n            pow2 <<= 1\n        self.first_leaf = pow2 - 1\n        self.t = [None] * self.first_leaf\n        self.t.extend(t)\n        self.t.extend((0, 0) for _ in range(pow2 - n))\n        for i in reversed(range(self.first_leaf)):\n            self.t[i] = f(self.t[2 * i + 1], self.t[2 * i + 2])\n    \n    def query(self, lpos, rpos):\n        l = lpos + self.first_leaf\n        r = rpos + self.first_leaf\n        res = f(self.t[l], self.t[r])\n        while (l - 1) // 2 < (r - 1) // 2:\n            if l & 1:\n                res = f(res, self.t[l + 1])\n            if not r & 1:\n                res = f(self.t[r - 1], res)\n            l = (l - 1) // 2\n            r = (r - 1) // 2\n        return res\n    \n    def get(self, pos):\n        i = pos + self.first_leaf\n        return self.t[i]\n    \n    \nclass Solution:\n    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:\n        r, c = 0, 0\n        rs = []\n        cs = []\n        for ch in s:\n            if ch == \'L\':\n                c -= 1\n            elif ch == \'R\':\n                c += 1\n            elif ch == \'U\':\n                r -= 1\n            else:\n                r += 1\n            rs.append((r, r))\n            cs.append((c, c))\n        rit = IntervalTree(rs)\n        cit = IntervalTree(cs)\n        \n        answer = []\n        \n        for i in range(len(s)):\n            lx, rx = i, len(s)\n            while lx < rx:\n                mx = lx + (rx - lx) // 2\n                rr = rit.query(i, mx)\n                cc = cit.query(i, mx)\n                if i:\n                    rstart = rit.get(i - 1)[0]\n                    cstart = cit.get(i - 1)[0]\n                else:\n                    rstart, cstart = 0, 0\n                if startPos[0] + rr[0] - rstart in range(n) and startPos[0] + rr[1] - rstart in range(n) and \\\n                    startPos[1] + cc[0] - cstart in range(n) and startPos[1] + cc[1] - cstart in range(n):\n                    lx = mx + 1\n                else:\n                    rx = mx\n            answer.append(lx - i)\n        \n        return answer\n```\n
['Python3']