Consider each distinct value separately. Say we are focused on $$$x$$$ and denote the indices where $$$x$$$ occurs in $$$a$$$ as $$$b_1, b_2, \ldots, b_k$$$. We want to count the number of subarrays that covers at least one element in $$$b$$$. Let's break $$$[1, n]$$$ into intervals separated by each $$$b_i$$$, so we have intervals $$$[1, b_1], [b_1 + 1, b_2], \ldots, [b_{k-1} + 1, b_k]$$$.

We can consider each interval independently. Suppose the left bound of our subarray lies in $$$[b_i + 1, b_{i+1}]$$$, then the right bound of our subarray must contain at least $$$b_{i+1}$$$, so it can lie anywhere in $$$[b_{i+1}, n]$$$. Therefore, we have $$$(b_{i+1} - b_i) \cdot (n - b_{i+1} + 1)$$$ choices of subarrays for this fixed interval.

We can iterate over all intervals and add the product — this is the contribution for this integer $$$x$$$. Additionally, these subarrays are clearly distinct because their left bound is restricted to different, disjoint intervals. To obtain the answer, We can iterate over all distinct $$$x$$$ and add up the contributions. This is equivalent to the original $$$d(a, b)$$$ function because each distinct $$$x$$$ contributes $$$1$$$ to this function.

https://cses.fi/paste/2d15c9c12179f830d3d8d7/ $$$\mathcal{O}(n)$$$

Let's solve an easier problem. Consider this: You are given an array of $$$n$$$ integers and an integer $$$k$$$. Count the number of ways to split the array into continuous segments of lengths at most $$$k$$$.

Let $$$dp[i]$$$ denote the number of ways to split the prefix of length $$$i$$$. Our transition is simply $$$dp[i] = \sum_{j=1}^{\min(i,k)} dp[i-j]$$$, since we are adding the number of ways over all lengths $$$j \in [1, k]$$$ that the previous segment could be. Our base case is $$$dp[0] = 1$$$.

Going back to the actual problem. The only difference is that our segments has to contain all distinct elements, and we need to know the maximum length that our current segment can be. We can initialize a variable $$$l$$$ that tracks the minimum left bound such that the segment $$$a_l, \ldots, a_i$$$ contains all distinct elements.

We can initialize a map $$$\texttt{lst}$$$ that tracks the last encounter of each integer. Our segment cannot contain two of any integer, so at each index $$$i$$$ we should set $$$l = \max(l, \texttt{lst}[a[i]] + 1)$$$. Now it's the same problem as our easy problem. Our transition is simply $$$dp[i] = \sum_{j=l}^{i-1} dp[j]$$$.

https://cses.fi/paste/66e4b8951387ad02d3d9b1/ $$$\mathcal{O}(n \log n)$$$. Note that $$$\mathcal{O}(n)$$$ is perfectly possible using prefix sums but I was lazy.

You should recursively build the permutation until you successfully make a permutation of length $$$n$$$. At each step, find the minimum number that satisfies the difference greater than one condition and add it to the permutation. It turns out the number of backtracking calls is not that many before you find a valid permutation.

https://cses.fi/paste/4044f0215e650326d4383f/ $$$\mathcal{O}(n \log n)$$$

In bubble sort, if a smaller element is to the right of a larger number, it is swapped. Then, the bubble sort moves past the larger number. You can see that in each iteration, the smaller number only gets moved one spot left towards its correct position in the sorted array. Also, note that bubble sort is stable — it guarantees not to change the relative order of elements that compare equal.

Let's denote array $$$b = \texttt{sorted}(a)$$$. We want to find the maximum difference between each $$$a_i$$$ and its corresponding position in $$$b$$$. Since bubble sort is stable, we also must match the same numbers to $$$b$$$ in the same relative position in $$$a$$$.

https://cses.fi/paste/df74b084e298a14cd3f447/ $$$\mathcal{O}(n \log n)$$$

Read the solution to the previous problem for the bubble sort observation.

For this problem, $$$a[i]=$$$ the smallest untaken (i.e. not taken by previous positions) number among $$$a_1, \ldots, a_{i+k}$$$. This is because we cannot swap any numbers after index $$$i+k$$$ with only $$$k$$$ rounds. Any untaken numbers to the left of $$$i$$$ will also bubble past $$$i$$$ as smaller numbers are swapped to the left of $$$i$$$.

https://cses.fi/paste/681585dabfba0bd2d3f3a7/ $$$\mathcal{O}(n \log n)$$$

Let's inspect the manhattan distance formula. For each free campsite $$$f$$$, we should find the maximum value of $$$|x_r - x_f| + |y_r - y_f|$$$. A very common technique to deal with absolute value signs break it up into cases. For example,

Since we have two absolute value signs, there are $$$4$$$ cases we need to consider. Specifically:

All four cases can be done with sweep line and a segment tree. Consider the first case. If we know $$$x_f + y_f$$$, then we want to query for the minimum value of $$$x_r + y_r$$$ such that $$$x_r \geq x_f \text{ and } y_r \geq y_f$$$. We can we sort all the points such the $$$x$$$ inequality holds and query in a way such that the $$$y$$$ inequality holds. A relevant usaco.guide module

https://cses.fi/paste/1ddc2ecc75f59ff5d45f32/ $$$\mathcal{O}((n+m) \log (n+m))$$$

Let's prime factorize $$$k$$$ into $$$p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_m^{e_m}$$$. Let's look at each prime $$$p_i$$$ separately. We can guarantee $$$lcm(a_i, a_{i+1}) = k$$$ if the maximum of adjacent powers of $$$p_i$$$ is equal to $$$e_i$$$. For a single prime $$$p_i$$$, we must count the number of arrays $$$b$$$ of length $$$n$$$ such that $$$0 \leq b_i \leq e_i$$$ and $$$\max(b_i, b_{i+1}) = e_i$$$. Let's try to do this with DP.

Let $$$dp[i][j]$$$ denote the number of ways to make an array of length $$$i$$$ with $$$j$$$ as a boolean denoting whether $$$b_i = e_i$$$. We have:

• $$$dp[i][0] = dp[i-1][1] \cdot e_i$$$. This is because $$$b_{i-1} = e_i$$$ must hold if $$$b_i \neq e_i$$$. Here $$$b_i$$$ can take any integer $$$\in [0, e_i-1]$$$.

• $$$dp[i][1] = dp[i-1][0] + dp[i-1][1]$$$. We know this $$$b_i = e_i$$$ so it is just the sum of all possible previous ways.

However, $$$k$$$ can be up to $$$10^9$$$ so this is just a standard case of matrix exponentiation. We must find a vector $$$M$$$ such that:

It should be simple to see that

So the answer is simply stored in the entries of

.

Multiplying the number of ways over all $$$p_i$$$ yields the answer.

https://cses.fi/paste/73e8bad653ea3c2ad40ddc/ $$$\mathcal{O}(\text{fast enough})$$$

The same problem actually appeared in codeforces: 895C - Квадратные подмножества, but with vastly different constraints. However the solution is still highlighted by this comment.

Let $$$p_1, p_2, \ldots, p_k$$$ denote primes up to $$$5000$$$. It can be shown that $$$k \approx 670$$$. We can break down each number $$$a_i$$$ as a vector $$$v_i \in GF(2)^k$$$ such that $$$v_{i, j}$$$ denotes whether $$$v_i$$$ has an odd number of factors of $$$p_j$$$. We can see that a subset $$$S$$$ is the product of a perfect square if $$$\sum_{i \in S} v_i = 0$$$.

We can lay all $$$v_i$$$ as columns of a $$$k$$$ by $$$n$$$ matrix $$$M$$$ over $$$GF(2)$$$. Picking a subset corresponds to finding a vector $$$v \in {0,1}^n$$$ such that $$$Mv = 0$$$. This should remind you of the null space of $$$M$$$. Additionally, the nullity represents how many independent vectors there are in the null space, and we can choose any subset of them.

We can find the nullity of $$$M$$$ using the rank-nullity theorem. Let $$$r$$$ denote its rank, then we are looking for $$$n - r$$$. The answer is just $$$2^{n-r}$$$. We can find the rank of a matrix using Gaussian Elimination.

https://cses.fi/paste/c34e063a9ce96269d4328a/ $$$\mathcal{O}(nk^2)$$$

Consider the prefix sum array $$$p$$$. Each of the constraints $$$(l, r, s)$$$ represents $$$p_r - p_{l-1} = s$$$ or $$$p_r = p_{l-1} + s$$$.

Consider the graph with vertices from $$$0$$$ to $$$n$$$. We can add an edge from $$$(l-1) \rightarrow r$$$ with weight $$$s$$$ and an edge $$$r \rightarrow (l-1)$$$ with weight $$$-x$$$. We can start a DFS at any unvisited vertex and assign each element of $$$p$$$ with the sum of weights so far. If there is a conflict of assigned weights, then it is impossible.

We can extract the original array using $$$a_i = p_i - p_{i-1}$$$.

https://cses.fi/paste/7bcc5dba172caa2ad427fe/ $$$\mathcal{O}(n+m)$$$

Boring dijkstra.

https://cses.fi/paste/2ecb38a2d1c174c1d42893/ $$$\mathcal{O}(ab \log ab)$$$

We can notice that every operation preserves the total amount of water modulo $$$\gcd(a, b)$$$. Since both containers start with $$$0$$$ water, we can only have a total amount of water $$$t \equiv 0 \pmod{\gcd(a,b)}$$$ in any of the containers. Therefore, we just need to check $$$x \leq a$$$ and $$$x \equiv 0 \pmod{\gcd(a,b)}$$$.

https://cses.fi/paste/15e63aaa270cd243d428a7/ $$$\mathcal{O}(\text{skibidi})$$$

ABC 341G is an extremely similar problem. View the editorial for this for a much more detailed explanation.

We can think of each index $$$i$$$ as a point in the plane $$$(i, p[i])$$$ where $$$p$$$ is the prefix sum array. The problem becomes find the index $$$j$$$ that maximizes the slope from $$$pt_j$$$ to $$$pt_i$$$. Therefore, $$$pt_j$$$ should be the previous point on the upper convex hull.

https://cses.fi/paste/9e277db6d5eb2b2ed46c31/ $$$\mathcal{O}(\text{tralalero})$$$

Let's create an array $$$b$$$ where $$$b_i = x_i - a$$$. Now we know a subset $$$S$$$ has average $$$a$$$ if $$$\sum_{i \in S} b_i = 0$$$, Now we just need to use standard knapsack to find the number of subsets that sum up to $$$0$$$. Make sure to make the knapsack array at least length $$$2n500$$$ since $$$b$$$ can worst case have a sum of positive/negative $$$500n$$$,

https://cses.fi/paste/137f3e4836558116d42ad3/ $$$\mathcal{O}(n^3)$$$

Binary search for the average $$$x$$$. Then, find the maximum prefix of $$$a_i - x$$$ and $$$b_i - x$$$. If the sum of maximum prefixes across both arrays is at least $$$0$$$, then it is possible to choose an average at least $$$x$$$.

https://cses.fi/paste/e3956942d84fc717d42b04/ $$$\mathcal{O}(n \log A)$$$

Let's create an array $$$p_i$$$ where it stores the index of element $$$i$$$ in $$$a$$$. We can then replace the elements in $$$b$$$ with $$$p$$$ (i.e. set $$$b_i = p_{b_i}$$$). Now the problem turns into finding the longest increasing subsequence in $$$b$$$.

https://cses.fi/paste/b4931c61c6f863cdd42c80/ $$$\mathcal{O}(m \log n)$$$