A few years ago, I read this blog about policy-based data structures in C++ STL and how they can be utilised. Today is the first time I used them :)

The Solution

2129B - Stay or Mirror The problem is quite simple, for each element we are either greedily choosing between the inversions existing due to elements greater than it on its left side or the inversions created by applying the operation to it — these will be the elements greater than it to the right side.

The tutorial calculates these in $$$O(n^2)$$$ time by iterating over the array to calculate the values. However, we can do this in $$$O(n logn)$$$ time by using a balanced BST which can handle both insertions and queries for rank of an element in $$$O(logn)$$$ time. The rank of an element here means the number of elements in the set which are greater than the queried element.

Source: https://stackoverflow.com/questions/18093949/how-to-find-rank-of-an-element-in-stl-set-in-ologn

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
 
typedef tree<int,
             null_type,
             std::greater<int>,
             rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
 
void solve(int testCase) {
    ll i, a, n, ans = 0;
    cin >> n;
    ordered_set st;

    for (i = 0; i < n; i++) {
        cin >> a;
        ll b = st.order_of_key(a);
        st.insert(a);
        ans += min(b, n - a - b);
    }
    cout << ans << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t = 1;
    cin >> t;
    for (int testCase = 1; testCase <= t; testCase++)
        solve(testCase);
    return 0;
}

Submission: 332652788

I noticed that many people were confused by the mathematics used in the soltuion of the editorial of this Div2.C question and decided to share with you my easy method for solving it. I use the property of distributivity of the lcm fucnction over gcd to simplify the solution. For three integers $$$ a, b, c$$$ we have

• $$$ \gcd(lcm(a, b), lcm(a, c)) = lcm(a, \gcd(b, c))$$$
• $$$ lcm(\gcd(a, b), \gcd(a, c)) = \gcd(a, lcm(b, c)) $$$

Proof: GCD and LCM Distribute Over Each Other

Hence for an array of integers,

• $$$ \gcd(lcm(a_0, a_1), lcm(a_0, a_2) \dots lcm(a_0, a_n)) = lcm(a_0, gcd(a_1, a_2 \dots a_n)) $$$
• $$$ \gcd(lcm(a_1, a_2), lcm(a_1, a_3) \dots lcm(a_1, a_n)) = lcm(a_1, gcd(a_2, a_3 \dots a_n)) $$$
• $$$\dots$$$ $$$and$$$ $$$so$$$ $$$on$$$

Therefore, for every element of the array we can precalculate the $$$\gcd$$$ of its next elements. Then we can take the lcm of that precalculated value with the element and store it in a new array. This way all possible pairs will be covered. The answer of the problem will be the $$$\gcd$$$ of these elements. Time complexity of the $$$\gcd(m, n)$$$ function is $$$\log_2v$$$ where $$$v=\max(m, n)$$$. Hence, time complexity of the solution will be $$$O(n\cdot\log_2maxval)$$$ where $$$maxval$$$ is the maximum of the array. Here is the solution:

#include <bits/stdc++.h>
using namespace std;
 
long long lcm(long long a, long long b) { return (a*b)/__gcd(a, b); }
 
int main()
{
	long long n, ans=0;
	cin>>n;
	vector<long long> a(n), pregcd(n);
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	
	pregcd[n-2]=a[n-1];	
	for(int i=n-3; i>=0; i--)
		pregcd[i]=__gcd(pregcd[i+1], a[i+1]);
	
	for(int i=0; i<n-1; i++)
		pregcd[i]=lcm(pregcd[i], a[i]);
	
	for(int i=0; i<n-1; i++)
		ans=__gcd(ans, pregcd[i]);
	cout<<ans<<endl;	  
}

This is my first time writing a blog so suggestions are welcome! Edit: Changed the data type of variables from int to long long.