Problem idea: MGod
Problem preparation: zscoder
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)$$$
606535B - Rectangle Connections
Problem idea: CSQ31
Problem preparation: isaachew
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.
Problem idea: marvenlee
Problem preparation: marvenlee
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.
Subtask 4: $$$X \geq 0$$$ and $$$1 \leq a_i \leq 200$$$, for all $$$1 \leq i \leq n$$$
If $$$a_i$$$ is small, it hints at constructing a dynamic programming solution where the state/subproblem depends on the value of $$$a_i$$$. Let $$$dp[j]$$$ denote the length of the longest valid subsequence ending with element $$$j$$$. Initially, all $$$dp[j]$$$ are $$$0$$$. For each element $$$a_i$$$, we update $$$dp[a_i]$$$ by taking the maximum of $$$1 + dp[k]$$$ over all $$$k \lt X / a_i$$$. That is, $$$dp[a_i] = \max_{k \text{ such that } k \lt X / a_i} {(1 + dp[i - 1][k])}$$$
For readers who do not understand the design of the $$$dp$$$, you may read the explanation of the step in getting the $$$dp$$$ array.
If $$$a_i$$$ is small, it hints at constructing a dynamic programming solution where the state/subproblem depends on the value of $$$a_i$$$. Let $$$dp[i][j]$$$ denote the length of the longest valid subsequence within the prefix $$$[a_1, a_2, \dots, a_i]$$$, where the last element of the subsequence is $$$j$$$. The transitions are as follows:
- If $$$j \neq a_i$$$, then $$$dp[i][j] = dp[i - 1][j]$$$
- If $$$j = a_i$$$, then $$$dp[i][a_i] = \max_{k \text{ such that } k \lt X / a_i} {(1 + dp[i - 1][k])}$$$
Notice that the first dimension of the dp ($$$i$$$) only depends on the $$$i-1$$$, so we can compress the dimension by iterating over $$$i$$$ from 1 to $$$n$$$. Next, since the second dimension of the dp ($$$j$$$) is only affected if $$$j = a_i$$$. Hence, at each iteration of $$$i$$$, only the $$$j = a_i$$$ needs to be updated. Hence, we can maintain an array $$$dp$$$ of size $$$201$$$ (i.e., the maximum value of $$$a_i$$$), where at iteration $$$i$$$, $$$dp[j]$$$ stores the length of the longest valid subsequence with the last element of the subsequence is $$$j$$$. Then, we update $$$a_i$$$ to $$$\max_{k \text{ such that } k \lt X / a_i}$$$ (i.e., the length of the longest valid subsequence if we include $$$a_i$$$).
Time Complexity is $$$O(n\max{a_i})$$$
Subtask 5: $$$X \geq 0$$$ and $$$1 \leq a_i \leq 10^5$$$, for all $$$1 \leq i \leq n$$$
If $$$\max_{1\leq i \leq n}{a_i} = 10^5$$$, the subtask 4 solution will get a TLE verdict. We can understand the $$$dp$$$ constructed in subtask 4 in this way: at iteration $$$i$$$, the following operation is executed
- Range Maximum query (RMQ) — Query the maximum value from index $$$1$$$ to $$$X / a_i$$$.
- Point update — Update the value at index $$$a_i$$$ to the result of the previous query plus 1.
This can be efficiently implemented with a segment tree. Alternatively, since the range maximum query is always a prefix range (i.e., from $$$1$$$ to some value), we can use a Fenwick Tree with a slight modification to support maximum instead of sum.
Time Complexity: $$$O(n \log{\max_{1 \leq i \leq n}{a_i}})$$$
Subtask 6: $$$X \geq 0$$$ and $$$a_i \geq 1$$$, for all $$$1 \leq i \leq n$$$ If $$$\max_{1\leq i \leq n}{a_i} = 10^9$$$, the solution of subtask 5 would result in MLE because the array is too large. However, since the number of elements is at most $$$10^5$$$, there are at most $$$10^5$$$ distinct values. Thus, we can perform a coordinate compression by the following:
- Sort and duplicate the values of $$$a_i$$$ and $$$\left \lfloor{X / a_i} \right \rfloor$$$.
- Assign each unique value a compressed index via a map
We also include $$$\left \lfloor{X / a_i} \right \rfloor$$$ in the compressed array because in this way, both updates and queries are performed on compressed indices.
Time Complexity: $$$O(n \log{\max_{1 \leq i \leq n}{a_i}})$$$
Subtask 7: No additional constraints
Notice that $$$X$$$ and $$$a_i$$$ can be negative. After a thorough case discussion, we can conclude the following:
- If $$$a_i$$$ is positive, the RMQ query the maximum value from $$$-\infty$$$ to $$$\left \lfloor{X / a_i} \right \rfloor$$$ before coordinate compression.
- If $$$a_i$$$ is negative, the RMQ query the maximum value from $$$\left \lceil{X / a_i}\right \rceil$$$ to $$$\infty$$$
Thus, we apply two different ranges of RMQ for different cases. If a Fenwick tree is used, two Fenwick trees are created for each case discussed.
Time Complexity: $$$O(n \log{\max_{1 \leq i \leq n}{a_i}})$$$
Subtask 4-6: $$$X \geq 0$$$ and $$$a_i \geq 1$$$, for all $$$1 \leq i \leq n$$$
If all elements and $$$X$$$ are positive, we can use a greedy approach to solve the problem optimally. The strategy is as follows: Enumerate the array, and maintain the length of the subsequence and the last element of the subsequence at each step. At step $$$i$$$, 1. If the product of the last element in the subsequence and $$$a[i]$$$ does not exceed $$$X$$$, then it is optimal to include $$$a[i]$$$ in the subsequence. The length of the subsequence is increased by 1. 2. Otherwise, if $$$a[i]$$$ is smaller than the last element in the subsequence, then it is optimal to replace the last element in the subsequence with $$$a[i]$$$.
Intuition of the correctness: For both cases, if $$$a_i$$$ is not included in the subsequence, the resulting subsequence will be no longer than the subsequence that includes $$$a_i$$$. Thus, this approach ensures the longest valid subsequence is achieved by greedily including or replacing elements based on different cases.
The full rigorous proof of the correctness can be found here.
Time complexity: $$$O(n)$$$
Subtask 7: No additional constraints There are two cases to discuss.
Case 1: If $$$X$$$ is positive and $$$a_i$$$ can be negative
In this case, we can follow the same strategy as subtask 6, with one adjustment. When comparing $$$a[i]$$$ to the last element in the subsequence, we compare the absolute values instead of the values themselves. The proof of correctness can be found here.
Case 2: If $$$X$$$ is negative
When $$$X$$$ is negative, we notice that the neighbouring elements of any valid subsequence must have different parity. In this case, we maintain two different states during the enumeration:
- One for when the last element in the subsequence is positive.
- One for when the last element is negative.
Let $$$pos_{len}$$$ (resp. $$$neg_{len}$$$) be the length of the subsequence and $$$pos_{last}$$$ (resp. $$$neg_{last}$$$ be the value of the last element in the subsequence if the last element must be positive (resp. negative).
At each step $$$i$$$, if $$$a_i$$$ is positive, we check the following:
- If $$$a_i \cdot neg_{last} \leq X$$$ and $$$neg_{len} + 1 \gt pos_{len}$$$ , we update $$$pos_{len} = neg_{len} + 1$$$ and set $$$pos_{last} = a_i$$$.
- Otherwise, if absolute value of $$$a_i$$$ is greater than $$$pos_{last}$$$, we update $$$pos_{last}$$$ to $$$a_i$$$.
The intuition behind the strategy is as such: 1. Case 1 ensures that if, after including element $$$a_i$$$, the subsequence with the negative last element is longer, we prefer that subsequence by updating it. 2. Case 2 ensures that we always replace the last element with the greatest possible absolute value. It is because given any two neighbouring elements, let's say $$$a_i$$$ is the positive element and $$$a_j$$$ is the negative element, the constraint on them is $$$a_i \cdot a_j \leq X$$$. It follows that $$$a_i \cdot (-a_j) \geq (-X)$$$. This constraint contrasts with the one when $$$X$$$ is positive and hence can be proven using a similar method.
Time complexity: $$$O(n)$$$
Problem idea: Evirir
Problem preparation: Evirir
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)$$$.
Auto comment: topic has been updated by marvenlee (previous revision, new revision, compare).
Unofficial editorial for A, in case you really need something now.
Make a bruteforcer.
Simply bruteforce the process until you reach $$$300,000$$$ or more characters, then run a direct search from the start to the end as given by $$$l$$$ and $$$r$$$.
Time complexity: $$$O(r_{max})$$$
Subtask 1
There are many queries required to be performed, so the solution to subtask 1 fails. Can you construct a way to answer each query after some setup?
Do the solution to subtask 1, but create a prefix sum to quickly find the results of querying $$$l = 1$$$ and any possible $$$r$$$.
Time complexity: $$$O(r_{max}+Q)$$$
Subtask 2
Use a well-known way to extract a given range’s sum from a prefix sum.
Observe that an answer to the query of $$$(l,r)$$$ is the same as the difference between the answers to queries $$$(1,r)$$$ and $$$(1,l-1)$$$ (This is essentially just in the nature of how prefix sums work.). Therefore, it suffices to do the subtask 2 solution twice, and taking the difference of the results.
Time complexity: $$$O(r_{max}+Q)$$$
none!
We’ve never actually used any properties of the string beyond its construction. Can you find some properties of the string?
Given a string consisting of $$$x$$$ ones and $$$y$$$ zeroes, how many ones and zeroes will there be 1 second later?
Initially, start with $$$1$$$ one and $$$0$$$ zeroes. Now observe that every second, if you initially have $$$x$$$ ones and $$$y$$$ zeroes, all $$$x$$$ ones will become $$$x$$$ groups of “10” and all $$$y$$$ zeroes will become ones. Therefore, after one second you must then have $$$x+y$$$ ones and $$$x$$$ zeroes. Continue this until the total number of ones and zeroes you have is $$$r$$$, and you will get the number of ones in the range.
Time complexity: $$$O(Q log(r_{max}))$$$
Subtasks 3 and 4 (yes, you really don't need subtask 5 to 7)
You have code from Subtask 4 that tells you the number of ones and zeroes after every second. Run it and try finding a pattern.
After every second, the length of the string is a fibonacci number, and the number of zeroes and ones are the two previous fibonacci numbers.
There’s yet another “fibonacci recurrence” in the string. Observe strings with regards to the strings in the previous seconds.
These strings are “fibonacci words”; any string is the concatenation of the two strings before it.
Given a sufficiently large fibonacci word, split the fibonacci word into its two smaller components. How can you use this to compute some segment of the query?
We use the subtask 3 idea of splitting the query as the difference between the answer to $$$(1,r)$$$ and $$$(1,l-1)$$$. Now, let’s consider how we would answer the query $$$(1,r)$$$.
Observe that any characters after $$$r$$$ will not affect the answer, so we can use any prefix of the string that is at least $$$r$$$ characters long. Specifically, we will use a fibonacci word of length $$$F_{n}$$$ where $$$F_{n}$$$ refers to the $$$n$$$th fibonacci number for some sufficiently large $$$n$$$ (Using at most $$$F_{88}$$$ is sufficient for any possible $$$r$$$). Split the fibonacci word into two parts: $$$(1, F_{n})$$$ and $$$(F_{n}+1,r)$$$. We know that the number of ones in a fibonacci word of length $$$F_{n}$$$ is $$$F_{n-1}$$$ (see: hint 2), so we can immediately compute the first part of the query.
Now, observe that the second part of the query must necessarily be smaller than $$$F_{n-2}$$$ (otherwise, $$$F_{n}$$$ would’ve been too small to successfully encompass the query $$$(1,r)$$$) and that this part of the query must be in a fibonacci word of length $$$F_{n-2}$$$. However, we can treat this as being a query of $$$(1,r-F_{n-1})$$$ using a fibonacci word we know it must be inside, which is the same problem but smaller, thus recursion is possible!
One final note: In some parts of the recursion, the next query may not necessarily need to be in the $$$F_{n-2}$$$th fibonacci word, e.g. it can be in the $$$F_{n-3}$$$th word. This is perfectly fine, you can repeatedly split any fibonacci word $$$F_{k}$$$ into a $$$F_{k-1}$$$ word and a $$$F_{k-2}$$$ word and take the $$$F_{k-1}$$$ word while ignoring the $$$F_{k-2}$$$ word. This allows you to make sure that the fibonacci word that your query is in is the smallest one that fits, allowing you to eventually split the query into two again.
By precomputing the values of the fibonacci numbers, this allows us to compute each query in $$$O(log(r_{max}))$$$.
Time Complexity: $$$O(Q log(r_{max}))$$$
The reason why I didn’t explicitly discuss these subtasks are due to the fact that these subtasks bait a much harder approach! Specifically, subtask 5 can be solved using an implicit segment tree, however this solution would actually trick you into thinking that subtasks 6-8 are all segment tree or other, more complicated data structures, while the actual solution is a more insight based approach.
This is actually a type of system called a Lindenmayer system, or L-system for short.
Here’s a wikipedia article that mentions this topic. https://en.wikipedia.org/wiki/L-system (Note that the first example shown under "Examples of L-systems" is exactly the same system as in this problem, so in theory someone could google their way into this in contest. I doubt it though, unless the person already has knowledge in formal grammar and decided to google about formal grammar systems.)
Auto comment: topic has been updated by leg (previous revision, new revision, compare).