Solve four algorithmic coding tasks

You will solve four independent coding tasks:

1. Count equal-value pairs in an array: Given an integer array nums of length n, return the number of index pairs (i, j) with 0 ≤ i < j < n and nums[i] = nums[j]. Target time/space: O(n) time using O(n) auxiliary space. Explain the approach and complexity.
2. Simulate a match-three board with gravity: Given an R × C grid board of uppercase letters (colors) or '.' for empty. Repeatedly, in a single round, mark every cell that belongs to any horizontal or vertical run of length ≥ 3 of the same letter (runs can overlap). Remove all marked cells (set to '.'), then apply gravity so that in each column letters fall down and '.' move up. Repeat rounds until the board is stable (no removals). Return the final grid. Constraints: 1 ≤ R, C ≤ 50. Describe the algorithm and its complexity.
3. Check an X-pattern in a square matrix: Given an n × n integer matrix, return true iff every element on the main diagonal and the anti-diagonal is non-zero and every other element is zero; otherwise return false. Constraints: 1 ≤ n ≤ 100. Provide the check and complexity.
4. Process block placement queries on a line: You have N empty positions labeled 1..N. Process Q operations of two types:

• Place l r: mark all positions in the inclusive interval [l, r] as occupied (placing on already-occupied cells has no additional effect).
• Query k: return the leftmost starting index s such that there exists a contiguous unoccupied segment [s, s+k-1] of length k; if no such segment exists, return -1. Design a data structure to support up to N, Q ≤ 2×10^5 with near O((N + Q) log N) total time. Explain the data structures used and provide the algorithm.