Mancunian and Twin Permutations

★★★★★

4.7

3 votes

Binary Indexed Trees, Data Structures, Fenwick tree, Hard, Segment Trees

Details

Submissions

Discussion

Editorial

Problem

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.

Input:
The first line contains a single integer N denoting the number of elements in the arrays A and B.
The second line contains N integers denoting the elements of the array A.
The third line contains N integers denoting the elements of the array B.
The fourth line contains a single integer Q denoting the number of queries.
Each of the next Q lines contains the quadruplet L1 R1 L2 R2 for the i^th query.

Output:
For each query, output the answer in a new line.

Constraints:
1 <= N, Q <= 100000
1 <= A_i, B_i <= N
A and B are permutations of 1...N
1 <= L1 <= R1 <= N
1 <= L2 <= R2 <= N
R1 - L1 = R2 - L2

Sample Input

6
1 2 3 4 5 6
5 3 1 4 6 2
2
2 4 2 4
4 6 1 3

Sample Output

1
2

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Case 1: Swap the indices (1, 2) in the first array.
Case 2: Swap the indices (1, 4) and (3, 5).

Contributers:

Satyaki Upadhyay

Mitesh Agrawal