All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Consider a string T. A cyclic shift of the string T is a string T' obtained by moving an arbitrary (possibly, zero) number of T's symbols from the beginning to the end. For example, the string chef is a cyclic shift of the string hefc, but the string fehc is not a cyclic shift of the string chef.
The minimal cyclic shift of a string is the lexicographically smallest cyclic shift. For example, the minimal cyclic shift of the string hefc is chef.
You are given a string S. The string S is generated randomly, i.e. any character of S is chosen randomly from the set of lowercase Latin letters, independently of other characters.
You are also given Q queries - one of the following forms:
- 0 J C: make the Jth character of S equal to C. C will be chosen randomly from the set of lowercase Latin letters.
- 1 L R P: output the Pth character of the minimal cyclic shift of the string obtained by taking a substring of S from the Lth to the Rth characters, inclusively.
Your task is to handle these queries efficiently.
There is a single test case per test file.
The first line of input contains randomly generated string S, consisting of lowercase Latin letters.
The second line contains a single integer Q, denoting the number of queries.
Each of the following Q lines describe a single query in one of the formats described above.
For each query of the type 1 L R P, output a single line containing the Pth character of the minimal cyclic shift of a substring of S starting at the Lth character and ending at the Rth character.
- 1 ≤ |S| ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ L ≤ R ≤ |S|
- 1 ≤ J ≤ |S|
- 1 ≤ P ≤ R - L + 1
- C is a lowercase Latin letter, i.e. from 'a' to 'z'
- S consists of lowercase Latin letters
Input: codechef 5 0 6 q 1 5 7 1 1 3 8 3 0 5 m 1 2 8 7 Output: c e o
Example case 1. Let's perform all the queries one-by-one:
- Initially S = "codechef".
- In the first query we change the 6th letter of S to 'q', and it becomes equal to codecqef.
- In the second query, we're asked to find the 1st letter of the smallest cyclic shift of the string cqe. The smallest cyclic shift is cqe, and its' first letter is c.
- In the third query, we're asked to find the 3rd letter of the smallest cyclic shift of the string decqef. The smallest cyclic shift is cqefde, and its' third letter is e.
- In the fourth query we change the 5th letter of S, and it becomes equal to codemqef.
- In the fifth query, we're asked to find the 7th letter of the smallest cyclic shift of the string odemqef. The smallest cyclic shift is demqefo, and its' seventh letter is o.
|Tags||medium, segment-tree, snckpb16, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.