All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Earthquake in Bytetown! Situation is getting out of control!
All buildings in Bytetown stand on straight line. The buildings are numbered 0, 1, ..., N−1 from left to right.
Every hour one shake occurs. Each shake has 3 parameters: the leftmost building that was damaged during this shake, the corresponding rightmost building, and the force of the shake. Each time all the buildings in the disaster area are damaged equally. Let's consider this process in details.
At any moment every building has the number that indicates its height (may have leading zeroes). This number corresponds to some string consisting of digits. When some shake affects to the building its string circularly rotates to the left by the value of the force of the shake and its height corresponds to the value of new string. Pay attention that after rotation string may have leading zeroes. For instance: a building with height 950 got in disaster area with force 2, Then its string become 095, so height in reality is 95. If it was one more shake with force 1, then its height would become 950 again.
Major of Bytetown got some ideas how to protect residents, so sometimes he needs such kind of stats: find height of the highest building on some interval. You are given information about all the heights before the very first shake and then you get queries of two types:
- Type 0, described by 0 Li Ri Fi: Shake occurred on interval [Li, Ri] with force Fi.
- Type 1, described by 1 Li Ri: The major wants to know the biggest height on interval [Li, Ri].
Here, of course, the interval [L, R] contains all the building k such that L ≤ k ≤ R.
You want to get a promotion and promised to complete this task. Now it's time to do it!
Each test file contains only one test case.
The first line of input contains an integer N denoting the number of buildings in Bytetown. The second line contains N space-separated integers A0, A1, ..., AN−1 denoting the initial height of the buildings. The third line contains an integer M denoting the number of queries. Each of next M lines starts with 0 or 1, where 0 denotes a query Type 0 and 1 denotes a Type 1 query. If it's a Type 0 query then 3 integers follows Li, Ri, Fi, denoting number of the leftmost building, number of the rightmost building and force of this shake. If it's a Type 1 query then 2 integers follows Li, Ri, denoting numbers of the leftmost building and the rightmost building of necessary segment.
For each Type 1 query, output an integer denoting the answer for the query without leading zeroes.
- 1 ≤ N ≤ 800000 = 8 × 105
- 1 ≤ M ≤ 200000 = 2 × 105
- 0 ≤ Ai < 10000 = 104
- 0 ≤ Li ≤ Ri < N
- 0 ≤ Fi ≤ 60
- Ai does not have leading zeroes
Input: 3 17 3140 832 8 1 0 2 0 0 2 1 1 1 2 1 0 0 0 0 2 2 1 0 2 0 1 1 1 1 0 2 Output: 3140 1403 71 832 3140
The initial array: [17, 3140, 832].
The first query is a Type 1 query with numbers of buildings 0 and 2, so the answer is the maximum of the array: 3140.
The second query is a Type 0 query with numbers of buildings 0 and 2, and force 1, so the array turns to: [71, 1403, 328].
The third query is a Type 1 query again with numbers of buildings 1 and 2, so the answer is the maximum of 1403 and 328: 1403
|Tags||aug14, lazy, medium, pavel1996, segment-tree|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.