All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Distinct Integers in Range
Tag(s):

Advanced Data Structures, Bitset, Data Structures, Easy, Segment Trees

Problem
Editorial
Analytics

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 \le N \le 10^5$$
$$1 \le A[i], B[i] \le 5000$$
$$1 \le Q \le 10^5$$
$$1 \le a \le b \le N$$
$$1 \le c \le d \le 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
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NetApp

Challenge Name

CodeNet 2018

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?