Üç nəfər Prostokvaşinodan 2#4492
- Matroskin, mən seqment ağacı qurmağı öyrəndim. - Şarik, sənə hər cür boş şeylərdən daha yaxşı yeni bir it damı tikərdin. - Yaxşı Matroskin, mən artıq Dayı Fyodora kodu göstərmişəm, əvvəlki məsələdə baxa bilərsən, amma sənə yeni bir funksiya göstərəcəm — dəyişikliklərin edilməsi.
int update(int v, int left, int right, int pos, int val) { if (left == right) t[v] = val; return 0; int mid = (left + right) / 2; if (pos <= mid) update(v * 2, left, mid, pos, val); else update(v * 2 + 1, mid + 1, right, pos, val); t[v] = max(t[v * 2], t[v * 2 + 1]); return 0;}
- Yaxşı, Şarik, artıq funksiyanı yazdınsa, qulaq as. Mən sənə n qeyri-mənfi ədədlərdən ibarət massiv və iki növ sorğudan ibarət dəst verəcəyəm: əgər sorğunun növü birə bərabərdirsə, onda bir ədəd p gələcək və sən elə iki ədəd tapmalısan ki, l və r (1 \leq l \leq r \leq n), elə ki, aşağıdakı şəkildə çağırılan funksiya
get_max(1, 1, n, l, r)
dəyəri p-yə bərabər qaytaracaq. Əgər belə cütlərdən bir neçəsi varsa, l-in ən kiçik olduğu cütü çıxar, əgər belə bir neçəsi varsa, r-in ən kiçik olduğu cütü çıxar. Əgər belə cütlər yoxdursa, "Error" sətrini çıxar. Əgər sorğunun növü iki bərabərdirsə, onda iki ədəd x, y gəlir və funksiyanı aşağıdakı şəkildə işə salmaq lazımdır
update(1, 1, n, x, y)
Bu cür məsələnin öhdəsindən gələ bilərsənmi? Başlanğıcda əvvəlki məsələdən olan funksiyanın çağırıldığını qəbul etmək olar
build(1, 1, n)
ilə.
- Çalışacam, Matroskin.
Birinci sətrdə tək bir ədəd n (1 \leq n \leq 10^6) — massivdəki elementlərin sayı. İkinci sətirdə n qeyri-mənfi ədəd var, bunlar 10^9-u keçmir — massiv elementləri. Sonra m (1 \leq m \leq 10^5) — sorğuların sayı gəlir. Və sonra m sətir, hər biri ilk ədəd — sorğunun növü və sonra bir və ya iki ədəddən ibarət sorğunun təsviri ilə gəlir.
Hər bir 1 tipli sorğu üçün məsələnin cavabını çıxarın.
Nümunə 1