Subtask 1: For some constant $$$c$$$, $$$y_{i,1}=y_{i,2}=c$$$ for all $$$1\le i\le m$$$.

We can observe that as any two districts are on the same y-coordinate, they can be connected by a road, so the answer is 1 for every input in the subtask.

Subtask 2: $$$m\le2000$$$. $$$0\le x_{i,1},x_{i,2},y_{i,1},y_{i,2}\le2000$$$ for all $$$1\le i\le m$$$.

We can notice that each road we build must be within the same row or column, so we can build a graph where every district is connected to the rows or columns it occupies. To find the number of connected components, we can use DFS, DSU, or any other such algorithm.

Time complexity: $$$O(\left(w+h\right)\cdot m)$$$ where $$$w$$$, $$$h$$$ are the maximum width/height of a district.

Subtask 3: $$$m\le2000$$$.

We can construct a full graph of districts, with roads as edges, by checking every pair of districts to see if their x- or y-coordinate intervals overlap, with a time complexity of $$$O(m^2)$$$.

Subtask 4: $$$x_{i,1}=x_{i,2}$$$, $$$y_{i,1}=y_{i,2}$$$ for all $$$1\le i\le m$$$.

Notice that every district occupies one cell in the grid, as there is only one row and column that each district occupies. We can construct a partial graph, such that each district is connected to the previously considered district considered for that row or column, so that each row and column is fully connected. As the coordinates go up to $$$10^9$$$, we can use std::map to store the last districts considered, in $$$O(m \operatorname{log}m)$$$ time.

Subtask 5: $$$y_{i,1}=y_{i,2}=i$$$ for all $$$1\le i\le m$$$.

As the y-coordinates of districts never overlap, no roads can be built horizontally. We can sort them by increasing value of $$$x_1$$$, then keep track of the maximum value of $$$x_2$$$ so far. If the new district's $$$x_1$$$ is less than that, it overlaps and joins the current connected component.

Subtask 6: $$$x_{i,1}\le x_{(i+1),1}$$$, $$$y_{i,1}\le y_{(i+1),1}$$$ for all $$$1\le i\le m-1$$$.

We can do the same thing as in Subtask 5, but keep track of both the maximum value of $$$x_2$$$ and $$$y_2$$$ to determine if a district is connected, so the currently considered district is connected if it overlaps in either the x or y coordinate.

Subtask 7: No additional constraints.

We can sort the districts by their x and y coordinates separately, tracking which districts form a connected component in the graph consisting of either horizontal or vertical roads only. If the current district is determined to belong to the same connected component as the previous district considered, we can add an edge to the previous district. This ensures the connected components are still the same as if we constructed the full graph of horizontal/vertical roads. Then, we can combine the graphs for the horizontal and vertical roads, obtaining a graph with the correct connected components.

Let the currently queried subarray be $$$b = [b_1, b_2, \ldots, b_m]$$$.

Subtask 1: $$$n \le 15$$$, $$$q \le 120$$$

The problem is equivalent to partition $$$b$$$ into the maximum number of continuous subarrays such that the GCD of all subarrays are equal. If there are $$$k$$$ subarrays, then it takes $$$m - k$$$ operations. Brute force all $$$2^{m - 1}$$$ partitions.

Time complexity: $$$O(qn2^n)$$$.

Subtask 2: $$$n, q \le 300$$$

Observe that the final value of $$$b$$$ must be the GCD of all elements of $$$b$$$, because the GCD of $$$b$$$ is invariant (does not change) when we perform operations. Let $$$g$$$ be the GCD of $$$b$$$.

We can use dynamic programming. Let $$$dp(i)$$$ be maximum number of subarrays the first $$$i$$$ elements can be partitioned into such that the GCD of each subarray is $$$g$$$. Then

• $$$dp(0) = 0$$$,
• $$$dp(i) = -\infty$$$ if the GCD of the first $$$i$$$ elements is larger than $$$g$$$,
• $$$dp(i) = \max\limits_{1 \le j \le i} dp(j - 1) + 1$$$ over $$$j$$$ such that $$$\gcd(b_j, b_{j+1}, \ldots, b_i) = g$$$ otherwise.

Time complexity: $$$O(qn^2)$$$.

Subtask 3: $$$n, q \le 2000$$$

Observe that since $$$dp$$$ is increasing, only the maximum $$$j$$$ such that $$$\gcd(b_j, b_{j+1}, \ldots, b_i) = g$$$ is useful. In other words, the following greedy is correct: Let $$$l = 1$$$ be the leftmost index of our current subarray. For $$$i = 1, 2, \ldots, m$$$, if $$$\gcd(b_l, b_{l+1}, \ldots, b_i) = g$$$, then make $$$[b_l, b_{l+1}, \ldots, b_i]$$$ a subarray and set $$$l = i + 1$$$. Repeat until $$$i = m$$$. If the last subarray does not have GCD $$$g$$$, then we need to merge it with the last completed subarray. If we can make $$$x$$$ complete subarrays, then the answer is $$$m - x$$$.

Time complexity: $$$O(qn)$$$.

Subtask 4: For all $$$1 \le i \le n$$$, $$$a_i \le 2$$$

If $$$b$$$ is already all equal, the answer is $$$0$$$. Otherwise, the target GCD is $$$1$$$, and we need one operation for every $$$2$$$ in $$$b$$$ to merge it with a $$$1$$$. Thus, this reduces to counting the number of $$$1$$$'s (or equivalently, $$$2$$$'s) in a subarray of $$$a$$$ fast. We can use prefix sums on the array $$$c$$$ where $$$c_i = 1$$$ if $$$a_i = 1$$$ and $$$0$$$ otherwise. To determine whether $$$b$$$ is all equal, check whether there are $$$0$$$ or $$$m$$$ $$$1$$$'s with the prefix sums.

Time complexity: $$$O(n + q)$$$.

Subtask 5: For all $$$1 \le i \le n$$$, $$$a_i = 2^k$$$ for some integer $$$k \ge 0$$$

This is an extension of Subtask 4. The answer is $$$m - \text{(the frequency of the minimum value in }b)$$$. Note that $$$k \le \log_2 10^5 \le 17$$$, so just maintain $$$17$$$ prefix sums, one for each power of 2.

Subtask 6: $$$q = n$$$. For all $$$1 \le i \le q$$$, the $$$i$$$-th query is $$$(1, i)$$$

This can be read as: start with $$$b = []$$$, do this $$$n$$$ times: append an integer to $$$b$$$ and output the answer. This is actually almost Subtask 3. If the GCD of all integers in $$$b$$$ does not change after appending an integer to $$$b$$$, we can maintain the answer quickly. If the GCD changes, just recompute the answer from scratch.

This is fast enough because when an integer is appended, the GCD remains the same or decreases. If it decreases, it must be divided by at least 2, so it will decrease at most $$$O(\log a_1)$$$ times.

Time complexity: $$$O(n \log a_1)$$$.

Subtask 7: For all $$$1 \le i \le n$$$, $$$a_i \le 36$$$

We need to simulate Subtask 3's greedy fast for a subarray. Firstly, we can get the GCD of a subarray fast using a sparse table. This takes $$$O(n \log n)$$$ time for preprocessing and $$$O(1)$$$ time per query.

Let the current query be $$$(l, r)$$$. Let the GCD of the subarray from $$$l$$$ to $$$r$$$ be $$$g$$$. For an index $$$i$$$, let $$$\operatorname{nxt}(i)$$$ be the minimum $$$j \gt i$$$ such that the subarray from $$$i$$$ to $$$j - 1$$$ has GCD $$$g$$$. Then we want to answer the question: Let $$$x = l$$$, what is the maximum number of times we can set $$$x := \operatorname{nxt}(x)$$$ while $$$x \le r + 1$$$? This value is $$$x$$$ in Subtask 3's solution. How do we answer this quickly?

For a fixed index $$$i$$$ and GCD $$$g$$$, to compute $$$\operatorname{nxt}(i)$$$, we binary search and use the sparse table to query range GCDs. To answer how many times we can do $$$x := \operatorname{nxt}(x)$$$, we can use binary lifting and build a jump table.

Time complexity: $$$O(nA \log n)$$$, where $$$A = \max a_i$$$.

Subtask 8: No additional constraints

Subtask 6 is in fact a hint from Subtask 7 to 8. Observe that for a fixed index $$$l$$$, over all $$$r \ge l$$$, the GCD of the subarray from $$$l$$$ to $$$r$$$ takes on at most $$$O(\log a_l)$$$ values. Thus, if we only compute $$$\text{nxt}$$$ for those values, we only need to compute $$$O(n \log n \log A)$$$ values, where $$$A = \max a_i$$$. One can compress the values and binary search (much faster) or use an $$$\texttt{unordered_map}$$$ for storing and reading the jump table.

Time complexity: $$$O(n \log n \log A)$$$.