Davamlı məlumat strukturları#5626
Əgər davamlı məlumat strukturlarının nə olduğunu bilmirsinizsə, narahat olmayın — bu məsələni həll edə bilərsiniz.
Davamlı məlumat strukturları o strukturlardır ki, hər hansı bir dəyişiklikdən sonra belə əvvəlki versiyalara çıxış imkanı qalır. Tutaq ki, sizdə n elementdən ibarət bir ardıcıllıq var və p-ci elementi əvəz etmək lazımdır. Bunun üçün əvvəlki versiyadan yalnız p-ci elementi fərqlənən yeni bir versiya yaradırsınız. Nəticədə sizdə ardıcıllığın iki versiyası olacaq.
Bu məsələdə sizdən tələb olunan sadəcə m sorğunun icrası nəticəsində saxlanacaq ardıcıllıq versiyalarının sayını hesablamaqdır.
Birinci sətirdə iki ədəd n (1 \leq n \leq 100\,000) və m (1 \leq m \leq 100\,000) verilir. Burada n — ardıcıllıqda olan ədədlərin sayı, m — sorğuların sayı.
İkinci sətirdə n təbii ədəd verilir — ardıcıllığın özüdür.
Növbəti m sətirdə aşağıdakı sorğulardan biri verilir:
SET i p d — i-ci ardıcıllıqdan p-ci elementi d olan yeni bir ardıcıllıq yaratmaq;
GET i p — i-ci ardıcıllıqdan p-ci elementi götürmək.
Başlanğıc ardıcıllıq 0 nömrəsinə malikdir. Ardıcıllıqdakı mövqelər bir ilə başlayır. Mövcud olmayan versiyalara sorğular olmayacaq. Birinci tip sorğunun işlənməsi zamanı j+1 nömrəsini alan yeni bir versiya yaradılır, burada j — son əlavə edilmiş ardıcıllığın nömrəsidir, əvvəlcə j = 0.
Bir ədəd çıxarın — ardıcıllıq versiyalarının sayı.
Nümunə 1