Range Maximum Queries (Հատվածի մաքսիմալ արժեքի հարցումներ)
Ձեզ տրված է
n տարրերց կազմված զանգված և q հարցում։ Հարցումների երկու հիմնական տեսակ կա.- Գտնել տվյալ հատվածում (range) գտնվող տարրերի մաքսիմալ արժեքը
- Թարմացնել զանգվածի որևէ դիրքի արժեքը
Ձեր խնդիրն է ամեն效率 ցուցաբերելով մշակել այս հարցումները։
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n և q (1 ≤ n, q ≤ 100 000), որոնք համապատասխանաբար սահմանում են զանգվածի տարրերի քանակը և հարցումների քանակը:Երկրորդ տողում տրված են
n ամբողջ թվեր (), որոնք հանդիսանում են զանգվածի նախնական տարրերը:Հաջորդ
q տողերից յուրաքանչյուրն արտահայտում է մեկ հարցում.- Եթե հարցումը վերաբերում է հատվածի մաքսիմումին, տողը սկսվում է
1թվով, որի հետևից գալիս են թվեր և (): Սա ցույց է տալիս, որ մեզ հետաքրքրում է[l_i, r_i]միջակայքի ամենամեծ արժեքը:
- Եթե հարցումը նախատեսում է թարմացում, տողը սկսվում է
2թվով, որի հետևից գալիս են երկու թվեր և (): Այստեղp_i-ը սահմանում է զանգվածի այն դիրքը, որի արժեքը պետք է փոխարինելx_i-ով:
Ելք
Յուրաքանչյուր հատվածի մաքսիմումի հարցման դեպքում պետք է առանձին տողում տպել տվյալ հատվածում գտնվող մեծագույն արժեքը։
Օրինակ
Мուտք | Ելք |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 4
9
7 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB