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 100005

struct 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;
}