Üç nəfər Prostokvaşinodan 2
- 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 rəqəmlərdən ibarət bir massiv və iki növ sorğudan ibarət bir dəst verəcəm: əgər sorğunun növü birə bərabərdirsə, onda bir rəqəm p gələcək və sən elə iki rəqəm tapmalısan ki, l və r (1 ≤ l ≤ r ≤ N), belə ki, aşağıdakı şəkildə çağırılan funksiya
get_max(1, 1, N, l, r)
dəyəri p-ə 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çə varsa, r-in ən kiçik olduğu cütü çıxar. Əgər belə cütlər yoxdursa, "Error" sətirini çıxar. Əgər sorğunun növü iki bərabərdirsə, onda iki rəqəm 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.
Giriş verilənləri
Birinci sətir tək bir rəqəm N (1 ≤ N ≤ 10^6) – massivdəki elementlərin sayını ehtiva edir. İkinci sətirdə N qeyri-mənfi rəqəmlər var, bunlar 10^9-u keçmir – massiv elementləri. Sonra M (1 ≤ M ≤ 10^5) – sorğuların sayı gəlir. Və sonra M sətir, hər biri ilk rəqəm – sorğunun növü və sonra bir və ya iki rəqəmdən ibarət sorğunun təsviri ilə gəlir.
Çıxış verilənləri
Hər bir 1 tipli sorğu üçün məsələnin cavabını çıxarın.