Observation 1: We denote the string at time $$$t$$$ to be $$$S(t)$$$. Then $$$S(t) = S(t-1) + S(t-2)$$$ where $$$+$$$ represents string concatenation.

Proof: We proceed using mathematical induction. The base case $$$t=2$$$ can be easily proven by hand. For our inductive step, we wish to show that $$$S(t) = S(t-1) + S(t-2)$$$, given that the observation is true time $$$t-1$$$. We can split the string $$$S(t-1)$$$ into two sections, which are $$$S(t-2)$$$ and $$$S(t-3)$$$. By definition, performing the operation of replacing $$$1$$$ with $$$10$$$ and $$$0$$$ with $$$1$$$ on each of these parts will make the two parts $$$S(t-1)$$$ and $$$S(t-2)$$$ respectively, which in turn results in $$$S(t) = S(t-1) + S(t-2)$$$.

Subtask 1: $$$Q=1, r \leq 300 000$$$

The binary string can be generated by brute force, manually performing the operations until the length of the string exceeds $$$300 000$$$. The number of ones in the range $$$[l,r]$$$ can then be found by manually iterating through the string from indices $$$l$$$ to $$$r$$$.

Time complexity: $$$O(Qr_{max})$$$

Subtask 2: $$$l = 1, r \leq 300 000$$$

A prefix sum on the binary string can be created. The queries can then be answered in $$$O(1)$$$ time by simply accessing the element at index $$$r$$$ of the prefix sum.

Time complexity: $$$O(r_{max} + Q)$$$

Subtask 3: $$$r \leq 300 000$$$

Using the prefix sum from subtask 3, the queries can be answered in $$$O(1)$$$ time by subtracting the element at index $$$l-1$$$ from the element at index $$$r$$$ of the prefix sum.

Time complexity: $$$O(r_{max} + Q)$$$

Subtask 4: $$$l=1$$$, $$$r$$$ is equal to the length of the string after some integer number of seconds.

Let $$$f(t)$$$ be the number of ones in the binary string at time $$$t$$$. From Observation 1, we know that $$$f(0) = 1$$$, $$$f(1) = 1$$$, $$$f(t) = f(t-1) + f(t-2)$$$. We can then compute the values of $$$f$$$ using this recurrence relation until $$$f(t)$$$ exceeds $$$r_{max}$$$.

Time complexity: $$$O(Q\log_{\phi}(r_{max}))$$$

Subtask 5: $$$l = r$$$

Let $$$pos(t, i)$$$ be the character at the $$$i$$$th position of $$$S(t)$$$. If $$$i$$$ is larger than the length of $$$S(t-1)$$$ which is $$$F_{t}$$$, the character is in the second part of the string (the part which is equal to $$$S(t-2)$$$. In this case, $$$pos(t, i) = pos(t-2, i - F_{t})$$$. Otherwise, the character is in the first part of the string which is $$$S(t-1)$$$, so $$$pos(t, i) = pos(t-1, i)$$$. The answer is simply $$$pos(t_{max}, l)$$$, where $$$t_{max}$$$ is the smallest $$$t$$$ such that $$$F_{t+1} \geq 10^{18}$$$. We can recursively call the function $$$pos$$$ until we hit a base case of either $$$t = 0$$$ or $$$t = 1$$$.

Time complexity: $$$O(Q\log_{\phi}(r_{max}))$$$

Subtask 6: $$$Q=1$$$

Define $$$g(x)$$$ as the number of ones in the prefix $$$[1, x]$$$ of the binary string. We can split this prefix into the binary string at time $$$t$$$ and the remainder of the string, where $$$t$$$ is the largest time such that the length of $$$S(t)$$$ is less than $$$x$$$, as $$$S(t)$$$ is a prefix of all binary strings that come after it. Therefore, $$$g(x) = g(y) + g(x-y)$$$, where y is the largest Fibonacci number less than or equal to $$$x$$$. We can compute $$$y$$$ using either binary search or brute force.

Time complexity: $$$O(Q\log^2_{\phi}(r_{max}))$$$

Subtask 7: $$$r \leq 10^9$$$ and Subtask 8: No additional constraints.

Solution 1 (Evirir, LCJLY): Reusing our idea from Subtask 6, we can precompute all Fibonacci numbers up to $$$10^{18}$$$. The value of $$$g(x)$$$ can now be calculated by $$$g(x) = F_{y+1} + g(x-y)$$$ instead. Note that $$$y$$$ must be found using binary search for the time complexity to improve.

Time complexity: $$$O(Q\log_{\phi}(r_{max})\log(\log_{\phi}(r_{max})))$$$

Solution 2 (leg): Recursively calculate the number of ones over segment $$$[l,r]$$$ using a similar method to a segment tree. We start at the root of the segment tree, which in our case is $$$t_{max}$$$, and maintain the range of indices the current segment covers. The current segment then splits from $$$[a,b]$$$ into $$$[a,y]$$$ and $$$[y+1,b]$$$ using the same definition of $$$y$$$ as above. As we usually do in a segment tree, we immediately return $$$F_{t+1}$$$ if the current segment is entirely contained within $$$[l,r]$$$, and return $$$0$$$ if it is entirely outside of $$$[l,r]$$$.

Time complexity: $$$O(Q\log_{\phi}(r_{max}))$$$

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
vi fib;
vi spl;
int solve(int tl, int tr, int l, int r, int dep){
	if(l > r)return 0;
	if(tl == l && tr == r){
		// out4(tl, tr, l, r);
		// dout(dep);
		return fib[dep-1];
	}
	if(tr < l || tl > r)return 0;
	
	// out4(tl, tr, l, r);
	return solve(tl, tl + spl[dep], l, min(r, tl + spl[dep]), dep-1) + solve(tl + spl[dep] + 1, tr, max(tl + spl[dep] + 1, l), r, dep - 2);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	fib.pb(0);
	fib.pb(1);
	spl.pb(0);
	spl.pb(0);
	while(fib.back() <= 1e18){
		spl.pb(fib.back() - 1);
		fib.pb(fib.back() + fib[fib.size()-2]);
	}
	
	int t;
	cin>>t;
	while(t--){
		in2(a,b);
		a--; b--;
		out(solve(0, fib.back(), a, b, fib.size() - 1));
	}
}

Solution 3 (_ja): Observe that the $$$i$$$th one occurs at position $$$i \cdot \phi$$$. Therefore, the number of ones in segment $$$[l,r]$$$ is $$$\lfloor \frac{r+1}{\phi} \rfloor - \lfloor \frac{l}{\phi} \rfloor$$$. Note that this solution requires an extremely high precision value of $$$\phi$$$, so careful implementation is required to work around this.

Time complexity: $$$O(Q)$$$

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.

Subtask 1: $$$X = 10^{18}$$$

Since for any $$$1 \leq i \leq n$$$, we have $$$a_i \leq 10^9$$$. It follows that $$$a_i \times a_{i - 1} \leq 10^9 \times 10^9 = 10^{18} = X$$$. Therefore, the entire array is a valid subsequence. The longest valid subsequence is simply $$$n$$$.

Subtask 2: $$$n \leq 20$$$

We can apply a complete search algorithm by enumerating all possible subsequences. For each subsequence, we check whether it is valid by iterating through the array and verifying that the product of every pair of neighbouring elements does not exceed $$$X$$$. Among all the valid subsequences, we select the longest one as the solution. This can be implemented either recursively or using a bitmask.

Time complexity: $$$O(n \times 2^n)$$$

Subtask 3: $$$n \leq 10^3$$$

We can apply a dynamic programming solution (Similar to the Longest Increasing Subsequence problem). Let $$$dp[i]$$$ denote the length of the longest valid subsequence ending at position $$$i$$$ (i.e., within the array $$$[a_1, a_2, \dots, a_i]$$$), where $$$a_i$$$ must be included in the subsequence. To compute $$$dp[i]$$$, we apply the following transition:

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

There are two directions for solving the future subtasks.

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)$$$.