Միջակայքի նվազագույն և առավելագույն հարցում
Ձեզ տրված է
n էլեմենտներից բաղկացած զանգված և q հարցում։ Հարցումներն ունեն երկու տեսակ.- Հաշվել նվազագույնն ու առավելագույնը տրված միջակայքում
- Թարմացնել զանգվածի էլեմենտը որոշակի դիրքում
Ձեր նպատակը արդյունավետորեն մշակել այս հարցումները:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ
n և q (1 ≤ n, q ≤ 100000), որոնք ցույց են տալիս զանգվածի էլեմենտների քանակը և հարցումների քանակը, համապատասխանաբար։Մուտքի երկրորդ տողը պարունակում է
n ամբողջ թվեր (), որոնք հանդիսանում են զանգվածի նախնական էլեմենտները։Հաջորդ
q տողերից յուրաքանչյուրում ներկայացված է մեկ հարցում.- Եթե հարցումը مربوط է միջակայքի նվազագույն-առավելագույն զույգին, ապա տողը սկսվում է
1-ով, իսկ հետո տրված են երկու ամբողջ թվեր և (), որոնք ցույց են տալիս [] միջակայքը, որտեղ պետք է գտնել նվազագույնն ու առավելագույնը։
- Եթե հարցումը مربوط է զանգվածի էլեմենտի թարմացմանը, ապա տողը սկսվում է
2-ով, իսկ հետո տրված են երկու ամբողջ թվեր և (), որոնք նշանակում են, որ զանգվածի -րդ էլեմենտը պետք է փոխարինվի արժեքով։
Ելք
Յուրաքանչյուր միջակայքի նվազագույն-առավելագույն հարցման համար տպեք տվյալ միջակայքում գտնվող էլեմենտների նվազագույնն ու առավելագույնը տարբեր տողերում:
Օրինակներ
Մուտք | Ելք |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB