For each value $$$x$$$, we can include $$$0$$$ or $$$1$$$. If $$$f(x)$$$ is the number of times $$$x$$$ appears in the array, Then there are $$$f(x) + 1$$$ ways to pick $$$0$$$ or $$$1$$$ occurrences of $$$x$$$. Since every value is independent of every other values, we will take the product of $$$f(x) + 1$$$ over all $$$x$$$. This can be done with std::map or sorting.

Let $$$L_i$$$ be the nearest greater element on the left, and $$$R_i$$$ be the nearest greater element on the right. These can be calculated in $$$\mathcal{O}(n)$$$ with monotonic stack.

From the value $$$i$$$ we can go to any value in $$$[L_i + 1, R_i - 1]$$$ that's strictly smaller than $$$h_i$$$. So we will calculate the DP in increasing order of $$$h_i$$$. The formula will be:

We can calculate this with a segment tree. We also have to take care of duplicates by calculating them at the same time and then updating the segment tree.

There are plenty of solutions that are straight-forward greedy, but I will describe a nice solution that uses DP.

The most obvious DP is $$$dp(i, j)$$$ being the lexicographically smallest string if you start in the cell $$$(i, j)$$$. Obviously, $$$dp(i, j) = A_{i,j} + min(dp(i+1, j), dp(i, j+1))$$$. Unfortunately, this is $$$\mathcal{O}(n^3)$$$, since each string can be of length $$$n$$$. We need to somehow find a way to compare strings without storing them. The way to fix this is: compression!

Now instead of calculating $$$dp(i, j)$$$, we will calculate $$$ord(i, j)$$$, which will just be an integer satisfying the following condition:

for all $(i_1, j_1), (i_2, j_2)$ in the same diagonal.

To calculate some diagonal, we will take each cell $$$(i, j)$$$ and sort them according to $$$(A_{i,j}, min(ord(i+1,j), ord(i,j+1))$$$. $$$ord(i, j)$$$ will simply be the position of $$$(i, j)$$$ according to the sort.

This is $$$\mathcal{O}(n^2 \log n)$$$ using std::sort, and it gets TLE. However the log can be removed using radix sort.

Let $$$P_i$$$ be the nearest greater element on the right. This can be calculated with monotonic stack. Now the query becomes: "How many times can you perform the assignment $$$l = P_l$$$ while $$$l \le r$$$?". This can be solved with binary lifting.

This can be solved using merge sort tree. In each node of the segment tree, we will store all the elements in the range in nondecreasing order.

For each query, we will decompose it into $$$\mathcal{O}(\log n)$$$ nodes, and each node, we will count the number of values between $$$c$$$ and $$$d$$$ in $$$\mathcal{O}(\log n)$$$ using binary search. This way, we can answer each query in $$$\mathcal{O}(\log^2 n)$$$, which is fast enough.

Let $$$S_i$$$ be the nearest equal element on the right, or $$$∞$$$. If there's an $$$i$$$ in $$$[l, r]$$$ such that $$$P_i \le r$$$, then $$$a_i = a_{P_i}$$$. That means not all values in $$$[l, r]$$$ are distinct. To check if such $$$i$$$ exists in $$$[l, r]$$$, check the minimum $$$P_i$$$. This can be done with a segment tree.

In each update, $$$\mathcal{O}(1)$$$ values change, so it can done in $$$\mathcal{O}(\log n)$$$ per query.

The average prime gap is $$$\mathcal{O}(\log n)$$$. So the trivial solution actually works in $$$\mathcal{O}(\sqrt{n} \log n)$$$. It can also be done in $$$\mathcal{O}(\log n)$$$ using randomized primality checks.

Imagine a functional graph with $$$n$$$ edges of the form $$$i \rightarrow p_i$$$. Let $$$L_1, L_2, ..., L_k$$$. The answer will be LCM(L_1, L_2, ..., L_k). This can be calculated by factorizing in $$$\mathcal{O}(n \sqrt{n})$$$ or $$$\mathcal{O}(n \log n)$$$ with sieve.

This can be done with monotonic queue, which allows adding an element at the back, removing the element from the front, and extracting the minimum. https://cp-algorithms.com/data_structures/stack_queue_modification.html#queue-modification-method-1

This can be done with a std::map to maintain the frequency of each value.

This can be done with a std::map to maintain the frequency of each value, as we as a std::set containing (frequency, values) pairs.

This can be done with an array to maintain the frequency of each value (since only values $$$\le k$$$ are relevant for th mex), as well as a std::set of excluded values.

This can be done by maintaining the number of inversions and an ordered set.

When adding a new element $$$x$$$, we will add the number of elements greater than $$$x$$$ to the inversion counter (since $$$x$$$ is at the end of the subarray).

When removing an element $$$x$$$, we will subtract the number of elements less than $$$x$$$ to the inversion counter (since $$$x$$$ is at the start of the subarray).

Distinct values, mode, MEX, and inversions can all be solved using a segment tree and coordinate compression.

We can use mergesort. This uses $$$n \log n$$$ queries.

Let's query chair $$$1$$$ and chair $$$N$$$. If they're equal, then we have found a solution. Otherwise, we can solve using binary search.

Let's query chair $$$x = \frac{N+1}{2}$$$. If $$$x$$$ is odd and chair $$$1$$$ is equal to chair $$$x$$$, we can guarantee a solution in $$$[x, n]$$$. Same can be said if $$$x$$$ is even and chair $$$1$$$ is not equal to chair $$$x$$$. Otherwise, there always exists a solution in $$$[1, x]$$$.

This solution uses exactly $$$2 + \lceil \log_2 n \rceil$$$ queries, which is at most $$$20$$$.

There exists a path between $$$u$$$ and $$$v$$$ of length $$$w$$$ iff the shortest path between $$$u$$$ and $$$v$$$ with the same parity $$$w' \le w$$$.

Construct a graph with $$$2N$$$ nodes, each node representing a pair (node, parity of path length). For each edge $$$(u, v)$$$ we will add undirected edges between $$$(u, 0), (v, 1)$$$, and $$$(u, 1), (v, 0)$$$.

Now for a query $$$(u, v, w)$$$, we have to check if the shortest path between $$$(u, 0)$$$ and $$$(v, w \mod 2)$$$ has length less than or equal to $$$w$$$. These distances can be precalculated in $$$\mathcal{O}(n (n + m))$$$ with BFS.

For each $$$i$$$, let $$$P_i$$$ be the number of $$$j$$$ such that $$$j \lt i$$$ and $$$x_j \gt x_i$$$. The answer will be the maximum $$$P_i$$$, since during each round, $$$P_i$$$ decreases by $$$1$$$ for each $$$P_i \gt 0$$$.

Let's consider each prime factor of $$$k$$$ separately.

Let's say that we want to calculate the number of ways to place the prime $$$p$$$. Let's say the number of times $$$p$$$ appears in the factorization of $$$a_i$$$ is $$$c_i$$$. The condition from the statement is equivalent to $$$\max(c_i, c_{i+1}) = X$$$, where $$$X$$$ is the number of times $$$p$$$ appears in the factorization of $$$k$$$.

Let $$$dp_p(n)$$$ be the number of arrays $$$c$$$ of length $$$n$$$ such that $$$\max(c_i, c_{i+1}) = X$$$. There are two cases:

• $$$c_n = X$$$

• $$$0 ≤ c_n \lt X, c_{n-1} = X$$$

So $$$dp_p(n) = dp_p(n-1) + dp_p(n-2) \cdot X$$$. $$$dp_p(n)$$$ can be calculated by raising a matrix to the $$$n$$$-th power in $$$mathcal{O}(\log n)$$$.

We can calculate this for each prime and multiply them to get the final answer, since the primes are independent of each other.

Subtract $$$a$$$ from each value in the array. Now we must count the number of subsets with sum $$$0$$$. This can be done easily with DP.

$$$dp(i, sum)$$$ is the number of subsets of $$$x_1, x_2, ..., x_i$$$ that add up to 0. Obviously $$$dp(i, sum) = dp(i-1, sum) + dp(i-1, sum - x_i)$$$.

We can handle negative value sums by sorting the array decreasingly so that the sum never goes below $$$0$$$. The final answer is $$$dp(n, 0)$$$.

We can do binary search on answer.

To check if the answer is at least $$$x$$$, subtract $$$x$$$ from each value in the array. Now we have to choose two prefixes that add up to at least $$$0$$$. We greedily take the biggest prefix sum of $$$a$$$ and $$$b$$$.

Also, $$$x$$$ doesn't have to be an integer.

We will calculate $$$dp(k)$$$, which is the number of subsets with GCD being $$$k$$$.

$$$dp(k)$$$ will be all the subsets of elements that are divisible by $$$k$$$, subtracting the subsets that have GCD being greater than $$$k$$$, i.e. $$$2k, 3k$$$, so on. Therefore:

This seems like it's $$$\mathcal{O}(n^2)$$$ but in reality it's $$$\mathcal{O}(n \log n)$$$.