Replace
Tag(s):

Hard, Segment tree

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), 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...

Contributor Challenge Name

October Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Math > Linear Algebra
• Algorithms > Graphs
• Math > Counting
• Algorithms > String Algorithms
• Data Structures > Advanced Data Structures