CHM
Sizin vəzifəniz — Persistent Disjoint-Set-Unionu həyata keçirməkdir. Bu nə deməkdir?
Disjoint-Set-Union haqqında:
Əvvəlcə sizdə n element var. Siz 2 tip sorğulara cavab verməyi öyrənməlisiniz.
+ a b — a və b elementlərinin aid olduğu çoxluqları birləşdirin;
? a b — a və b elementlərinin hazırda eyni çoxluqda olub-olmadığını müəyyən edin.
Persistent haqqında:
İndi bizdə Disjoint-Set-Union məlumat strukturlarının bir neçə versiyası olacaq.
Sorğular belə görünəcək:
+ i a b — i-ci struktura sorğu, a və b elementlərinin aid olduğu çoxluqları birləşdirin. Bu zaman i-ci struktur dəyişməz qalır, yeni versiya yaradılır və ona yeni nömrə verilir (hansı? daha ətraflı oxuyun);
? i a b — i-ci struktura sorğu, a və b elementlərinin hazırda eyni çoxluqda olub-olmadığını cavablandırın.
Giriş verilənləri
Birinci sətirdə 2 ədəd N (1 ≤ N ≤ 10^5) və K (0 ≤ K ≤ 10^5) — elementlərin sayı və sorğuların sayı verilir. Əvvəlcə bütün elementlər müxtəlif çoxluqlarda yerləşir. Bu başlanğıc versiya strukturun nömrəsi 0-dır.
Daha sonra K sətir gəlir, hər birində növbəti sorğunun təsviri var. Sorğuların formatı yuxarıda təsvir edilmişdir. Sorğular 1-dən K-ya qədər tam ədədlərlə nömrələnir.
j-ci + i a b tipli sorğunu işləyərkən, yeni versiya j nömrəsini alacaq.
Mövcud olmayan versiyalara sorğular olmayacaq (j > i).
Çıxış verilənləri
Hər bir ? i a b tipli sorğu üçün ayrıca sətirdə YES və ya NO çıxış edin.