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


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