All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Circuit breaks Long into segments..



Long assumes herself (here Long is a girl) a good programmer...

She was reading DISJOINT SET UNION. Somehow, her counterpart Circuit comes to know about this and arranges a trap for Long.

Long is asked a question.

She is given a string S (made of lowercase letters) and Q queries will be asked over the string.

EACH QUERY is of 3 types.

Type 1

3 Integers is given as input for type 1 i.e b,c,k. You have to tell the character at the kth position when all the characters from indices b to c (both inclusive) in String S(indexing is 0 based) are used to make the lexicographically largest string of size c-b+1.

Note: s1 and s2 are two equal string and s2 is lexicoraphically greater than s1 iff the character at first point of difference in s2 has HIGHER ASCII Value. E.g. uyz > uxz since y>x.

Type 2

1 Integer b and 1 character x is given as input in type 2. You have to change the character at bth index in updated String with character x.

Type 3

You will be given 2 Integers b,c and 2 characters x,y. In this query, you have to change all the characters which are equal to x in range b to c (both index inclusive in updated string) to character y.

Note:- After each query of type 2 and 3, we get the updated string and further queries are to be done over the updated string.

Input:- 1<=N<=1e5


0 <=k<c-b+1

0<=b<=c< N

Each Query has either 4 Integer (a,b,c,k with a=1 for type 1) or 2 Integer with 1 character (a,b,x with a=2 for type 2) or 3 integers (a,b,c with a=3 for type 3) and 2 characters x,y.


For each query of type 1 , tell the character at kth place.

3 2 4 q d
3 7 8 r c
1 4 6 0
2 2 b
3 8 9 f n
1 1 3 0
1 7 8 1
1 3 6 2
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 366 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


Initializing Code Editor...
Your Rating:


This Problem was Asked in

National Institute of Technology Patna

Challenge Name

Valentine Breakup!

View All Notifications