HackerEarth Swapping numbers problem solution

In this HackerEarth Swapping numbers problem solution You are given a permutation p1,p2,...pn of numbers from 1 to n.

A permutation p1,p2,...,pn, beauty, is defined as the minimum number of adjacent swaps required to sort the permutation.

If it is allowed to swap two elements of the permutation (not necessarily adjacent) at most once, then what is the minimum beauty that you can get?

HackerEarth Swapping numbers problem solution.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 1e5 + 14;

int ans[MAX_N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    ans[1] = 1;
    for (int i = 2; i < MAX_N; ++i)
        ans[i] = i ^ ans[i - 2];
    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        int a[n], l[n], r[n];
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            --a[i];
            l[a[i]] = r[a[i]] = i;
        }
        for (int i = 0; i < n - 1; ++i) {
            l[i + 1] = min(l[i], l[i + 1]);
            r[i + 1] = max(r[i], r[i + 1]);
        }
        while (q--) {
            int ql, qr;
            cin >> ql >> qr;
            --ql;
            int lo = -1, hi = n;
            while (hi - lo > 1) {
                int mid = (lo + hi) / 2;
                (ql <= l[mid] && r[mid] < qr ? lo : hi) = mid;
            }
//            cerr << lo << '\n';
            cout << ans[lo + 1] << ' ';
        }#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 7030;

int a[N];

struct Fen{
    int fen[N];
 
    Fen(){
        memset(fen, 0, sizeof fen);
    }
 
    void add(int x, int v){
        for( ; x<N ; x += x&-x)
            fen[x] += v;
    }
 
    int get(int x){
        int ret=0;
        for(; x ; x -= x&-x)
            ret += fen[x];
        return ret;
    }
} f;

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n;cin >> n;
    for(int i=0 ; i<n ; i++)
        cin >> a[i];
    int invs=0, mx=0;
    for(int i=0 ; i<n ; i++){
        memset(f.fen, 0, sizeof f.fen);
        for(int j=i+1 ; j<n ; j++){
            if(a[i] > a[j]){
                invs ++;
                int mid = f.get(a[i]) - f.get(a[j]);
                mx = max(mx, 2*mid+1);
            }
            f.add(a[j], 1);
        }
    }
    cout << invs-mx << "\n";
}
        cout << '\n';
    }
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 7e3 + 14;

int n, p[maxn], go[maxn][maxn];
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    int inv = 0;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        for (int j = 0; j < i; ++j) {
            inv += p[j] > p[i];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1, greater = 0; j < n; ++j) {
            go[i][j] = greater;
            greater += p[j] > p[i];
        }
        for (int j = i - 1, greater = 0; j >= 0; --j) {
            go[i][j] = greater;
            greater += p[j] > p[i];
        }
    }
    int ans = inv;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j)
            if(p[i] > p[j]){
                ans = min(ans, inv - go[j][i] + (j - i - 1 - go[j][i]) + go[i][j] - (j - i - 1 - go[i][j]) - 1);
            }
    }
    cout << ans << '\n';
}