All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Rhezo and his array
Tag(s):

Data Structures, Hard

Problem
Editorial
Analytics

Rhezo got an array $$A$$ as a gift from his friend Tanya. Along with this array, she also gave him a list of operations to perform on the array. The operations that are present in the list are the following.

$$1.$$ Three integers $$L, R$$ and $$X$$ are known, and Rhezo multiplies all numbers in the range $$[L, R]$$ by $$X$$.

$$2.$$ Four integers $$L, R, X$$, and $$Y$$ are known, and Rhezo needs to find out the count of integers in the range $$[L, R]$$ whose product with $$X$$ gives a number greater than or equal to $$Y$$.

Now, you being Rhezo's friend, have to help him in simulating the $$Q$$ operations and report the answer to any operation of type $$2$$. Please help poor Rhezo!

Input:
First line of input contains two integers, $$N$$ and $$Q$$ separated by a single space, denoting the number of elements in the array and number of operations to be performed respectively.
Next line contains $$N$$ single space separated integers denoting the elements of array $$A$$.
Each of the next $$Q$$ lines contain four or five space separated integers depending upon the query type.

  • If the $$1^{st}$$ integer is $$1$$, then it is a type $$1$$ operation and next three integers denote $$L, R$$ and $$X$$ as mentioned above.
  • If the $$1^{st}$$ integer is $$2$$, then it is a type $$2$$ operation and next four integers denote $$L, R, X$$ and $$Y$$

Output:
For each operation of type $$2$$, report the number of elements in range $$[L, R]$$ whose product with $$X$$ gives a number greater than or equal to $$Y$$.

Constraints:

  • $$1 \le N \le 5 \cdot 10^4$$
  • $$1 \le Q \le 10^5$$
  • $$1 \le A_i \le 10^{9}$$
  • $$1 \le L \le R \le N$$
  • $$2 \le X \le 10^{9}$$
  • $$1 \le Y \le 10^{9}$$

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

For the first query, only the number $$10$$ at index $$10$$ gives a number greater than or equal to $$20$$ when multiplied by $$2$$.

For the third query, only the numbers $$3, 4$$ and $$5$$ at indices $$3, 4$$ and $$5$$ respectively give a number greater than or equal to $$7$$ when multiplied by $$3$$.

Time Limit: 2.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, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

December Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications