PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You have the array A = [0].
Process M updates to it, of two types:
- Let M = \text{MEX}(A). Insert M at the beginning of A, i.e. A\gets [M] + A.
- Append A to itself, i.e. A\gets A + A.
After each operation, find the number of inversions in A.
EXPLANATION:
First, let’s look at the values of the sequence.
It’s not hard to see that at any point of time, the set of distinct integers present in A will be \{0, 1, 2, \ldots, K\} for some integer K.
This can be seen inductively - the sequence starts off as [0], and then:
- If the distinct elements are \{0, 1, 2, \ldots, K\}, the mex of the sequence is K+1.
Inserting K+1 makes the distinct elements \{0, 1, 2, \ldots, K+1\} so the invariant is maintained. - Duplicating the sequence obviously doesn’t change the set of distinct elements, so again the invariant is maintained.
What this means is that whenever the MEX is inserted by the first operation, it will always be strictly larger than every existing element of A.
Now, let’s look at how each operation changes the inversion count.
Let N denote the length of A.
First, inserting the MEX at the beginning.
As noted earlier, the MEX will always be strictly larger than every existing element.
So, it will form an inversion with every existing element too - and these are the only new inversions that form.
That means, the number of inversions will increase by the length of A, which is N.
As long as we’re able to maintain the value of N, this update is very easy to perform.
Maintaining the length is of course trivial: inserting the MEX increases the length by 1, and appending the sequence to itself doubles the length.
That leaves us with the doubling operation.
There are a couple of different ways to deal with this.
Solution 1
Let A' = A + A denote the doubled array.
The length of A' is 2N.Now, observe that any pair of indices (i, j) in A, will correspond to several pairs in A'.
Specifically, we’ll have the indices [i, j, N+i, N+j], and all pairs among these four indices.
Let’s now figure out how the contribute to inversions.
For this, it’s useful to consider separately the relative values of A_i and A_j.
That is,
- If A_i = A_j, then all the values at these four indices will be equal, and there are no inversions.
- If A_i \lt A_j, exactly one pair will be an inversion: namely (j, N+i).
- If A_i \gt A_j, three pairs will form inversions: (i, j), (i, N+j), (N+i, N+j).
So, if we have c_1 pairs of indices (i, j) in A such that A_i \lt A_j, and c_2 pairs such that A_i \gt A_j, the number of inversions in the doubled array A' will equal c_1 + 3c_2.
All we need to do now is maintain the values of c_1 and c_2.First off, c_2 is simply the inversion count itself, and we’re already maintaining that anyway.
As for c_1, you can use the same logic (of seeing which pairs in A correspond to which pairs in A') to see that after doubling the array, the new value of c_1 will be 3c_1 + c_2.That is, the doubling operation simply transforms the pair (c_1, c_2) to (3c_1 + c_2, c_1 + 3c_2).
The number of inversions is, of course, the second element of the pair.Note that we also need to update c_1 and c_2 when the MEX operation is performed, but this is easy: c_1 doesn’t change, and c_2 increases by N.
In summary, we have a very simple-to-implement solution.
Let N denote the length of A, c_1 denote the number of pairs (i, j) such that A_i \lt A_j, and c_2 denote the number of pairs (i, j) such that A_i \gt A_j.
Initially, N = 1 and c_1 = c_2 = 0.
Then,
- For a type 1 operation:
- c_2 increases by N.
- N increases by 1.
- c_1 doesn’t change.
- For a type 2 operation:
- c_1 changes to 3c_1 + c_2.
- c_2 changes to c_1 + 3c_2.
Note that the changes to c_1 and c_2 must be done simultaneously: you shouldn’t update one and then update the other with the new value.- N changes to 2N.
After each update, the answer is the value of c_2.
Solution 2
An alternate solution uses the additional constraint imposed on the operations: that the length of the sequence won’t exceed 10^9.
The doubling operation doubles the length of A, and so cannot happen more than \log 10^9 times. This means, if we’re able to process each such operation reasonably fast (say, in \mathcal{O}(M) time), we’ll have a fast enough solution.There are a few different ways of doing this, here’s one of them.
Let \text{freq}[x] denote the number of occurrences of x in A, and \text{Inv} denote the number of inversions in A.
When A is appended to itself, observe that there are three types of inversions:
- Inversions in the “left half”, i.e. the first copy of A.
There are \text{Inv} such inversions.- Inversions in the “right half”, i.e. the second copy of A.
Again, there are \text{Inv} such inversions.- Inversions where one element is from the left half and one is from the right half.
This is what we need to count.For the third case, consider some element x in the left half.
x will then form an inversion with every element smaller than it in the right half: which is just every element smaller than x in A.
There are \text{freq}[0] + \text{freq}[1] + \cdots + \text{freq}[x-1] such elements in total, along with \text{freq}[x] ways to choose the position of x itself in the left half.
So, the number of “crossing” inversions simply equals\sum_{x=0}^M \text{freq}[x] \cdot \left(\sum_{y=0}^{x-1} \text{freq}[y] \right)This is very easy to compute in \mathcal{O}(M) time, since the inner summation is just a prefix sum of the \text{freq} array.
The only thing we need to do is to keep the \text{freq} array updated properly.
This is, however, quite easy:
- When the MEX is appended, only one frequency changes; so update it.
- The doubling operation also just doubles every frequency.
This can be done directly in \mathcal{O}(M), since we’re spending \mathcal{O}(M) work at each such operation anyway to compute the answer.
TIME COMPLEXITY:
\mathcal{O}(M) or \mathcal{O}(M\log{10^9}) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int m; cin >> m;
vector <int> f(m + 1, 0);
f[0] = 1;
int ans = 0;
int eq = 0;
int p = 1;
int len = 1;
for (int i = 1; i <= m; i++){
int t; cin >> t;
if (t == 1){
ans += len;
len++;
f[p]++;
p++;
} else {
ans *= 2;
ans += len * (len - 1) / 2;
ans -= eq;
for (int i = 0; i < p; i++){
eq -= f[i] * (f[i] - 1) / 2;
f[i] *= 2;
eq += f[i] * (f[i] - 1) / 2;
}
len *= 2;
}
cout << ans << " \n"[i == m];
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
m = int(input())
n, c1, c2 = 1, 0, 0
ans = []
for t in map(int, input().split()):
if t == 1:
c2 += n
n += 1
else:
c1, c2 = 3*c1 + c2, 3*c2 + c1
n *= 2
ans.append(c2)
print(*ans)