Gözəllik Permutasiya Sorğuları#11732
Problem 0-indeksli hesablamadan istifadə edir, yəni, massivlər -dan başlayaraq nömrələnir.
uzunluğunda bir permutasiya, hər bir elementin dəqiq bir dəfə göründüyü və -dan n-1-ə qədər olan hər bir ədədin mövcud olduğu müsbət tam ədədlərdən ibarət bir massivdir. Məsələn, , [0,2,1], [0,3,1,2] permutasiyalardır, [0,1,3], , [0,1,0] isə deyil.
Biz permutasiya -nin çata bilən transformasiyalar dəstini dset -ə görə aşağıdakı əməliyyatı istənilən sayda ( ola bilər) tətbiq etməklə əldə edilə bilən permutasiyaların dəsti kimi müəyyən edirik:
İki indeks (0 \le i, j \le n-1) seçin ki, i \oplus j \in S olsun və permutasiya -nin və mövqelərindəki elementləri dəyişdirin.
Burada, bitwise XOR əməliyyatını ifadə edir.
Dset permutasiya -yə görə yaxşıdır adlanır əgər permutasiya -nin çata bilən transformasiyalar dəsti kimlik permutasiyasını ehtiva edirsə.
Biz uzunluğunda bir permutasiyanı kimlik permutasiya adlandırırıq əgər aşağıdakı şərt ödənilirsə: a_i = i (0 \le i \le m-1).
Permutasiya -nin gözəlliyi onunla bağlı yaxşı dset -nin minimum ölçüsü kimi müəyyən edilir.
Sizə uzunluğunda bir permutasiya verilir. Siz permutasiyanın ilkin gözəlliyini çıxarmalısınız. Sizə sorğu da verilir. Hər bir sorğu iki ədəd -dən ibarətdir. Hər bir sorğudan sonra, və mövqelərindəki elementləri dəyişdirməlisiniz. Qeyd edin ki, permutasiya hər bir sorğudan sonra dəyişiklikləri saxlayır. Hər bir sorğuya cavab olaraq, nəticə permutasiyasının gözəlliyini çıxarmalısınız.
Birinci sətirdə iki ədəd (1 \le n \le 5 \cdot 10^5) və (0 \le \beta \le 1) var.
İkinci sətirdə ədəd p_i (0 \le p_i < n) — başlanğıc permutasiya.
Üçüncü sətirdə bir ədəd (0 \le q \le 5 \cdot 10^5) — sorğuların sayı.
Sonrakı sətirdə iki ədəd a_i', b_i' (0 \le a_i', b_i' \le n-1) verilir — -ci sorğunun parametrləri.
-ci sorğunun dəyərləri aşağıdakı kimi müəyyən edilir. əvvəlki sorğunun cavabı, ya da bu birinci sorğu olarsa, ilkin permutasiyanın gözəlliyi olsun. Onda a_i = (a_i' + last \cdot \beta) \bmod n, və b_i = (b_i' + last \cdot \beta) \bmod n.
Birinci sətirdə, ilkin permutasiyanın gözəlliyini çıxarın.
Sonrakı sətirdə, sorğuların cavablarını çıxarın.
Nümunə
İkinci sorğudan sonra, permutasiya [5, 2, 1, 3, 4, 0, 6] olur.
S = \{3, 6\} olsun. Bu dəstdən istifadə edərək, permutasiyanı kimlik permutasiyasına çevirmək üçün aşağıdakı dəyişiklikləri edə bilərik:
i = 0 və j = 3 dəyişdirin. Permutasiya [\textbf{3}, 2, 1, \textbf{5}, 4, 0, 6] olur.
i = 3 və j = 5 dəyişdirin. Permutasiya [3, 2, 1, \textbf{0}, 4, \textbf{5}, 6] olur.
i = 1 və j = 2 dəyişdirin. Permutasiya [3, \textbf{1}, \textbf{2}, 0, 4, 5, 6] olur.
i = 0 və j = 3 dəyişdirin. Permutasiya [\textbf{0}, 1, 2, \textbf{3}, 4, 5, 6] olur.
Sübut etmək olar ki, |S| \le 1 olan əməliyyatlarla kimlik permutasiyasını əldə etmək mümkün deyil.
( bal): n \le 8, \beta = 0;
( bal): n \le 32, q = 0, \beta = 0;
( bal): garanti edilir ki, cavab -dən çox olmayacaq, \beta = 0;
( bal): n \cdot q \le 9 \cdot 10^6, \beta = 0;
( bal): q \le 10^4;
( bal): \beta = 0;
( bal): əlavə məhdudiyyət yoxdur.