# HackerEarth Mancunian and Twin Permutations problem solution

In this HackerEarth Mancunian and Twin Permutations problem solution You are given two arrays A and B of the same length N. Each is a permutation of the integers from 1 to N. You are allowed to perform operations on the first array. Each operation consists of swapping the values at any two indices in the first array.

There will be Q queries. Each query is specified by a quadruplet (L1,R1,L2,R2) which asks for the minimum number of swaps you need to perform in the first array so that the subarray [L1,R1] in the first array is a permutation of the subarray [L2,R2] in the second array.

## HackerEarth Mancunian and Twin Permutations problem solution.

`#include <bits/stdc++.h>#define LEFT(n) (2*(n))#define RIGHT(n) (2*(n)+1) using namespace std;struct Node{    int cnt;    Node *left, *right;    Node(){}    Node(int cnt, Node *left, Node *right){        this->cnt = cnt;        this->left = left;        this->right = right;    }     Node* insert(int s, int e, int val);};const int N = 100002;int n, arr[N], pos[N];Node *null = new Node(0, NULL, NULL);Node* root[N]; Node* Node::insert(int s, int e, int val){    if(val<s || val>e)  return this;     if(s == e)  return new Node(this->cnt+1, null, null);     int mid = (s + e)/2;    Node* resultant = new Node(this->cnt+1, this->left->insert(s, mid, val), this->right->insert(mid+1, e, val));    return resultant;}  int query(Node *a, Node *b, int s, int e, int lo, int hi){        if(s > e || lo > e || s > hi || lo > hi)    return 0;    if(s >= lo && e <= hi)  return b->cnt - a->cnt;     int mid = (s + e)/2;    return query(a->left, b->left, s, mid, lo, hi) + query(a->right, b->right, mid+1, e, lo, hi);}int main(){     ios_base::sync_with_stdio(0);    cin.tie(0);    cin>>n;    assert(n >= 1 && n <= 100000);    for(int i=1;i<=n;i++){        int val;        cin>>val;        pos[val] = i;    }    for(int i=1;i<=n;i++){        cin>>arr[i];        arr[i] = pos[arr[i]];    }    null->left = null->right = null;    root[0] = null;    for(int i=1;i<=n;i++){        root[i] = root[i-1]->insert(1, n, arr[i]);    }    int q;    cin>>q;    assert(q >= 1 && q <= 100000);    while(q--){        int l1, r1, l2, r2;        cin>>l1>>r1>>l2>>r2;        assert(l1 >= 1 && l1 <= r1 && r1 <= n);        assert(l2 >= 1 && l2 <= r2 && r2 <= n);        assert(r1 - l1 == r2 - l2);        cout<<(r2-l2+1) - query(root[l2-1], root[r2], 1, n, l1, r1)<<endl;    }    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define N 100005struct Q{    int l,r,idx,add,ans_idx;    Q(int l, int r, int idx, int add, int ans_idx) :     l(l), r(r), idx(idx), add(add), ans_idx(ans_idx) {}};int BIT[N], arr[N], pos[N], ans[N];vector<Q> queries;void bit_update(int idx, int val){    while(idx < N){        BIT[idx] += val;        idx += idx & (-idx);    }}int bit_query(int idx){    int ans = 0;    while(idx){        ans += BIT[idx];        idx -= idx & (-idx);    }    return ans;}bool cmp(Q a, Q b){    return a.idx < b.idx;}int main(){    int i, j, n, q, l1, r1, l2, r2, it;    scanf("%d", &n);    for(i = 1; i <= n; i++){        scanf("%d", &arr[i]);        pos[arr[i]] = i;    }    for(i = 1; i <= n; i++){        scanf("%d", &arr[i]);        arr[i] = pos[arr[i]];    }    scanf("%d", &q);    for(i = 0; i < q; i++){        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);        queries.push_back(Q(l1, r1, r2, -1, i));        queries.push_back(Q(l1, r1, l2 - 1, 1, i));        ans[i] = (r1 - l1 + 1);    }    sort(queries.begin(), queries.end(), cmp);    it = 0;    for(auto el : queries){        while(it + 1 <= el.idx){            it++;            bit_update(arr[it], 1);        }        ans[el.ans_idx] += el.add * (bit_query(el.r) - bit_query(el.l - 1));    }        for(i = 0; i < q; i++)        printf("%d\n", ans[i]);    return 0;}`