Ağac#4325
Kök ağacını nəzərdən keçirək. Başlanğıcda ağac yalnız bir kökdən ibarətdir. Hər bir zirvənin oğulları üçün soldan sağa doğru sıra müəyyən edilir. Ağac üzərində icazə verilən əməliyyatlar bunlardır:
Ağaca yarpaq əlavə etmək.
Ağacdan yarpaq silmək.
İki yarpaq arasında yolda olan zirvələrin sayını tapmaq.
İki yarpaq arasında "yol altı" zirvələrin sayını tapmaq.
"Yol altı" zirvələr, və yarpaqları arasında aşağıdakı kimi müəyyən edilir. Onların arasındakı u = w_0 - w_1 - \ldots - w_k = v yolunu nəzərdən keçirək. Bu yolda hər iki kənarın oğullarına doğru getdiyi w_c zirvəsini seçək. Qoy müəyyənlik üçün bu kənarlardan sol tərəfdəki bizi zirvəsinə, sağ tərəfdəki isə zirvəsinə yaxınlaşdırsın. Onda "yol altı" olan zirvələr aşağıdakı kimidir:
w_c zirvəsinin w_{c-1} və w_{c+1} arasında yerləşən bütün oğulları və onların alt ağaclarının bütün zirvələri;
i = 1, 2, \ldots, c-1 üçün — w_i zirvəsinin w_{i-1} oğulundan sağda yerləşən bütün oğulları və onların alt ağaclarının bütün zirvələri;
i = c+1, c+2, \ldots, k-1 üçün — w_i zirvəsinin w_{i+1} oğulundan solda yerləşən bütün oğulları və onların alt ağaclarının bütün zirvələri.
Ağacı əlavə və silmə sorğularına uyğun olaraq yenidən quran və yol və "yol altı" zirvələrin sayını tapmaq üçün sorğulara cavab verən bir proqram yazın.
Giriş faylının ilk sətirində bir tam ədəd — sorğuların sayı (0 \leq n \leq 300\,000) verilir. Növbəti sətirdən hər biri bir sorğunu təsvir edir. Mümkün sorğu növləri bunlardır:
l x — yeni yarpağı zirvəsinin ən sol oğulu kimi əlavə et.
r x — yeni yarpağı zirvəsinin ən sağ oğulu kimi əlavə et.
a x y — yeni yarpağı zirvəsinin oğulu kimi əlavə et, hansı ki, zirvəsinin dərhal sağında yerləşir; -dən sağda olan bütün zirvəsinin oğulları əlavə edildikdən sonra yeni zirvənin sağında yerləşir; zirvəsinin zirvəsinin oğulu olduğu təmin edilir.
d x — zirvəsini sil. Bu anda zirvəsinin silinmədiyi və yarpaq olduğu təmin edilir.
p x y — və arasında, o cümlədən bu zirvələrin özləri də daxil olmaqla, yolda olan zirvələrin sayını tap; və yarpaqlar olduğu təmin edilir.
q x y — və arasında, o cümlədən bu zirvələrin özləri də daxil olmaqla, "yol altı" zirvələrin sayını tap; və yarpaqlar olduğu təmin edilir.
Əlavə edilən zirvələr sorğularda əlavə edildiyi ardıcıllıqla birdən nömrələnir. Ağacın kökü nömrəsinə malikdir və heç bir zaman yarpaq hesab edilmir.
Sorğuları ardıcıllıqla icra edərək, p və ya q növündən olan hər bir sorğuya cavabı ayrıca bir sətirdə yazın.
Nümunə 1