All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Mr. Gora and his clever techniques
Tag(s):

Medium

Problem
Editorial
Analytics

Mr. Gora is extremely disappointed with the performance of the students in his subject.

He felt that something was AMISS. Therefore, he decided to conduct another NIGHT SHOW (lab exam :P ) for his students to test their basic understanding of the subject.

The question was extremely "simple".

The students are initially provided an array with no elements at all. (the indexing of the array is 1-based).

The students are provided with some queries as follows -

  • Type 1: Consider the first index in the array which is unallocated i.e empty. Place the integer K at that index.
  • Type 2: Consider all the indices between L and R (inclusive of L and R as well). Find the number of all the integers less than K in this range.
  • Type 3: Consider all the indices between L and R (inclusive of L and R as well). Find the number of all the integers equal to K in this range.
  • Type 4: Consider all the indices between L and R (inclusive of L and R as well). Find the number of all the integers greater than K in this range.

Students have to solve this question anyhow to pass the exam.
You being an excellent coder have to help these students.

Input

The first line of the input contains an integer Q denoting the number of the queries. Q lines follow. The queries are of the following form.

  • Query 1 is like "1 K" .
  • Query 2 is like "2 L R K" .
  • Query 3 is like "3 L R K" .
  • Query 4 is like "4 L R K" .

Output

For each query of type 2, 3 and 4, you need to output answer on a separate line.

Constraints

1<=Q<=6*105
1<=K<=109
Let M be the number of elements in the array before any particular query.
1<=L<=R<=M

Problem Setter - Shivam Garg

SAMPLE INPUT
10
1 4
1 5
1 7
1 4
2 1 3 4
3 2 4 5
1 6
4 1 5 4
2 4 5 5
2 2 4 7
SAMPLE OUTPUT
0
1
3
1
2
Explanation

10 queries are provided.
Query 1 The first unallocated index is 1. So 4 is placed there.
Query 2 The first unallocated index is 2. So 5 is placed there.
Query 3 The first unallocated index is 3. So 7 is placed there.
Query 4 The first unallocated index is 4. So 4 is placed there.
Query 5 In the range 1 to 3, we have no integer less than 4. So, the output is 0.
Query 6 In the range 2 to 4, we have 1 integer equal to 5. So, the output is 1.
Query 7 The first unallocated index is 5. So 6 is placed there.
Query 8 In the range 1 to 5, we have 3 integers greater than 4. So, the output is 3.
Query 9 In the range 4 to 5, we have 1 integer less than 5. So, the output is 1.
Query 10 In the range 2 to 4, we have 2 integer less than 7. So, the output is 2.

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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications