Schönheitspermutationsabfragen#11732
Das Problem verwendet 0-Indexierung, d.h. Arrays sind ab 0 nummeriert.
Eine Permutation der Länge ist ein Array von positiven ganzen Zahlen, in dem jedes Element genau einmal vorkommt und jede Zahl von bis n-1 vorhanden ist. Zum Beispiel sind , [0,2,1], [0,3,1,2] Permutationen, während [0,1,3], , [0,1,0] keine Permutationen sind.
Wir definieren die Menge der erreichbaren Transformationen der Permutation in Bezug auf die Menge als die Menge der Permutationen, die aus durch Anwendung der folgenden Operation beliebig oft (möglicherweise 0) erhalten werden können:
Wählen Sie zwei Indizes i, j(0 \le i, j \le n-1), so dass i \oplus j \in S, und tauschen Sie die Elemente der Permutation an den Positionen und .
Hierbei bezeichnet die bitweise XOR-Operation.
Die Menge wird als gut in Bezug auf die Permutation bezeichnet, wenn die Menge der erreichbaren Transformationen der Permutation eine Identitätspermutation enthält.
Wir nennen eine Permutation der Länge eine Identitätspermutation, wenn Folgendes gilt: a_i = i(0 \le i \le m-1).
Die Schönheit der Permutation wird als die minimale Größe einer guten Menge in Bezug auf sie definiert.
Sie erhalten eine Permutation der Länge . Sie müssen die anfängliche Schönheit der Permutation ausgeben. Außerdem erhalten Sie Abfragen. Jede Abfrage besteht aus zwei Zahlen . Nach jeder Abfrage müssen Sie die Elemente an den Positionen und tauschen. Beachten Sie, dass die Permutation die Änderungen nach jeder Abfrage beibehält. Als Antwort auf jede Abfrage müssen Sie die Schönheit der resultierenden Permutation ausgeben.
Die erste Zeile enthält zwei Zahlen n(1 \le n \le 5 \cdot 10^5) und \beta(0 \le \beta \le 1).
Die zweite Zeile enthält Zahlen p_i(0 \le p_i < n) — die Ausgangspermutation.
Die dritte Zeile enthält eine Zahl q(0 \le q \le 5 \cdot10^5) — die Anzahl der Abfragen.
In den folgenden Zeilen werden zwei Zahlen a_i', b_i'(0 \le a_i', b_i' \le n-1) angegeben — die Parameter der -ten Abfrage.
Die Werte der -ten Abfrage werden wie folgt bestimmt. Lassen Sie die Antwort auf die vorherige Abfrage sein oder die Schönheit der ursprünglichen Permutation, wenn dies die erste Abfrage ist. Dann gilt a_i = (a_i'+last \cdot \beta) \mod n, und b_i = (b_i'+last \cdot \beta) \mod n.
In der ersten Zeile geben Sie die Schönheit der ursprünglichen Permutation aus.
In den folgenden Zeilen geben Sie die Antworten auf die Abfragen aus.
Beispiel
Nach der zweiten Abfrage wird die Permutation zu [5, 2, 1, 3, 4, 0, 6].
Sei S = \{3, 6\}. Mit dieser Menge können wir die folgenden Tauschoperationen durchführen, um die Permutation in die Identitätspermutation zu transformieren:
Tauschen Sie i = 0 und j = 3. Die Permutation wird zu [\textbf{3}, 2, 1, \textbf{5}, 4, 0, 6].
Tauschen Sie i = 3 und j = 5. Die Permutation wird zu [3, 2, 1, \textbf{0}, 4, \textbf{5}, 6].
Tauschen Sie i = 1 und j = 2. Die Permutation wird zu [3, \textbf{1}, \textbf{2}, 0, 4, 5, 6].
Tauschen Sie i = 0 und j = 3. Die Permutation wird zu [\textbf{0}, 1, 2, \textbf{3}, 4, 5, 6].
Es kann bewiesen werden, dass es unmöglich ist, die Identitätspermutation durch Operationen mit |S| \le 1 zu erhalten.
( Punkte): n \le 8, \beta = 0;
( Punkte): n \le 32, q=0, \beta = 0;
( Punkte): es ist garantiert, dass die Antwort nicht überschreitet, \beta = 0;
( Punkte): n \cdot q \le 9\cdot10^6, \beta = 0;
( Punkte): q \le 10^4;
( Punkte): \beta = 0;
( Punkte): keine zusätzlichen Einschränkungen.