Solve four OA algorithm problems

You are given four independent coding questions. ## 1) Count square subgrids (multiple queries) For each query, you are given two integers `R` and `C` representing an `R × C` grid of unit cells. Return the total number of **axis-aligned square subgrids** (of all possible side lengths) that can be formed inside the grid. - **Input:** `q` queries, each query contains `R, C`. - **Output:** For each query, output the number of square subgrids. - **Constraints (typical):** `1 ≤ q ≤ 2e5`, `1 ≤ R, C ≤ 1e9`. --- ## 2) Minimum adjacent swaps to make a palindrome You are given a string `s` of length `n` (in the OA it may be a binary string such as only `'O'` and `'I'`, but assume it can be any characters). In one move, you may swap two **adjacent** characters. Return the **minimum number of adjacent swaps** needed to rearrange `s` into a palindrome. - If it is impossible to form a palindrome, return `-1`. --- ## 3) Row-major grid walk with obstacles, teleports, and loop detection You are given an `n × m` grid. You start at the top-left cell `(0,0)` and want to reach the bottom-right cell `(n-1,m-1)`. Movement rule (row-major walk): - From `(r,c)`, your next step is normally: - `(r, c+1)` if `c+1 < m` - otherwise wrap to the start of the next row `(r+1, 0)` if `r+1 < n` Additional rules: - Some cells are **blocked** (obstacles). If you ever step onto a blocked cell, stop and return `-1`. - Some cells are **teleporters**. If you step onto a teleporter cell, you are immediately moved to its paired destination cell. - Treat teleporting as part of the same “step”: each transition (including landing on a teleporter and being transported) counts as **one step total**. - If the process enters a cycle and will never reach the target, return `-2`. Return the number of steps to reach `(n-1,m-1)` if reachable. --- ## 4) Longest subarray under a prefix-sum inequality You are given an array `a` of length `n` (assume `a[i] ≥ 0`) and an integer `k`. Let prefix sums be: - `pref[0] = 0` - `pref[i+1] = pref[i] + a[i]` Find the maximum length of a subarray `[l, r)` (with `0 ≤ l < r ≤ n`) such that: \[ \text{pref}[r] - 2\cdot\text{pref}[l] \le k \] Return this maximum length.