All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Replace
Tag(s):

Hard

Problem
Editorial
Analytics

Yet another interesting problem about queries!

You have an array of n integers and q queries on this array. There are two types of queries:

  1. 1 \(a_i\) \(b_i\) \(x_i\) \(y_i\) - change all occurrences of \(x_i\) to \(y_i\) on the segment \([a_i, b_i]\)
  2. 2 \(a_i\) \(b_i\) \(x_i\) - count number of occurrences of \(x_i\) on the segment \([a_i, b_i]\)

This problem will be very popular! So you should solve it before before it became mainstream.

Input format

The first line of input contains two space separated integers n and q (\(1 \leq n, q \leq 5 \cdot 10^5\)) - size of array and number of queries.

The second line of input contains n space separated integers \(a_i\) (\(1 \leq a_i \leq n\)) - the elements of the array before queries.

Then q lines follow. The i-th of them contains parameters of the i-th query.

The i-th line can be:

  • 1 \(a_i\) \(b_i\) \(x_i\) \(y_i\) (\(1 \leq a_i \leq b_i \leq n\), \(1 \leq x_i, y_i \leq n\)) - parameters for first type query or
  • 2 \(a_i\) \(b_i\) \(x_i\) (\(1 \leq a_i \leq b_i \leq n\), \(1 \leq x_i \leq n\)) - parameters for second type query

Output format

For each query of second type print number of occurrences of \(x_i\) on the segment \([a_i, b_i]\).

SAMPLE INPUT
4 3
3 2 1 2
2 2 4 2
1 2 4 1 2
2 2 4 2
SAMPLE OUTPUT
2
3
Explanation

Initially array is \([3, 2, 1, 2]\).

First query: there are 2 occurrences of 2 on segment \([2, 4]\).

Second query changes array to \([3, 2, 2, 2]\).

Third query: there are 3 occurrences of 2 on segment \([2, 4]\).

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), TypeScript, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

October Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?