All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Convoluted Operations
Tag(s):

Compression, Data Structures, Easy-Medium, Fenwick Tree

Problem
Editorial
Analytics

Mishki is quite interested in playing games, and recently she found an empty stack. Now she wants to perform $$3$$ types of operations on the stack:

$$1)$$ $$1 \; A$$ : push element A in the stack.
$$2)$$ $$0$$ : pop one element from stack.
$$3)$$ $$2 \; K \; X$$ : find how many elements were less than $$X$$ present in the stack, after performing $$K^{th}$$ operation on the stack.

Can you help her in performing the above operations ?

Input:
The first line contains an integer $$N$$, denoting the number of operations.
Next $$N$$ line contains, any of the $$3$$ types of operations mentioned above, where $$i^{th}$$ line contains the $$i^{th}$$ operation.

Output
Print the required answer for each of the $$3^{rd}$$ type of operation, in new line.

Constraints:
$$1 \le N \le 5 \times 10^5$$
$$0 \le A, X \le 10^9$$
$$1 \le K \le N$$

Notes:
1) No pop operation will be given for an empty stack.
2) Let's say, you are performing $$i^{th}$$ operation on the stack and it is of $$3^{rd}$$ type, then the given $$K$$ will always be less than $$i$$.
3) There will be at least one $$3^{rd}$$ type of operation, in the input.

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

enter image description here

In $$3^{rd}$$ operation you need to find the values present in the stack which were less than $$10$$ , after performing $$2^{nd}$$ operation. So the answer is $$2$$.

enter image description here

In $$5^{th}$$ operation you need to find the values present in the stack which were less than $$5$$ , after performing $$4^{th}$$ operation. So the answer is $$2$$.

enter image description here

In $$7^{th}$$ operation you need to find the values present in the stack which were less than $$5$$ , after performing $$6^{th}$$ operation. So the answer is $$1$$.

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

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications