All Tracks>Data Structures> Advanced Data Structures> Segment Trees> Problem
Distinct Integers in Range
★★★★★

4.1

32 votes
Advanced Data Structures, Bit Manipulation, Data Structures, Easy, Segment Trees
Problem

You are given two arrays A and B each of length N. Now you are given Q queries. In each query, you are given two pairs of ranges i.e. a range [a,b] in the array A and range [c,d] in the array B. For each query, you need to count distinct elements in the array which is formed by combining elements of the both the ranges in the query.

Input
The first line contains an integer N as input. 
Next line contains N space separated integers that denote elements of the array A.
Next line contains N space separated integers that denote elements of the array B.
Next line contains an integer Q that denotes the total number of queries.
Next Q lines contain 4 integers each i.e. a,b,c and d.

Output
For each query, you need to print the output in a new line. 

Constraints
1≤N≤105
1≤A[i],B[i]≤5000
1≤Q≤105
1≤a≤b≤N
1≤c≤d≤N

Sample Input
5
1 2 3 4 5
2 1 3 1 4
2
1 3 4 5
1 3 3 5
Sample Output
4
4
Time Limit: 2
Memory Limit: 1024
Source Limit:
Explanation

In query 1, the new array formed will be: 1 2 3 1 4 which contains four distinct elements.
In query 2, the new array formed will be: 1 2 3 3 1 4 which also contains four distinct elements.

Contributers:
Editor Image

?