Contexte

« Mon enfant, si je te donnais les richesses de trois vies et de trois existences, accepterais-tu d’apprendre ? »

Aujourd’hui, 玛德琳 et 坏德琳 se sont retrouvées devant une machine féerique. Elle contient des boules de quatre couleurs, chacune ayant son utilité. Les boules bleues sont les plus simples : rebondir dessus vous permet d’effectuer une ruée. Les boules roses sont une version améliorée : rebondir dessus vous permet d’effectuer deux ruées. Rebondir sur une boule blanche ne donne aucune ruée. Après un premier rebond, une boule jaune se couvre de piquants et vous ne pouvez plus la toucher.

Les niveaux de cette machine peuvent être décrits par une suite de couleurs. 玛德琳 et 坏德琳 y jouent depuis longtemps, sans avoir réussi à terminer le premier niveau. Alors, 玛德琳 éclate en sanglots ! Elle décide de tricher à l’aide d’un logiciel de modification ! Ce logiciel est très particulier : il ne peut modifier que les boules blanches et jaunes, et ne peut les transformer qu’en boules bleues ou roses ; de plus, la position de la boule modifiée à chaque étape est fixée. Lorsque 坏德琳 l’apprend, elle décide d’empêcher 玛德琳 de tricher. Elle pirate donc le logiciel et obtient le droit de modifier la couleur des boules jaunes. Par ailleurs, 玛德琳 pense qu’une suite de boules identiques rend le niveau plus facile. Elle définit la facilité d’un niveau comme la longueur maximale d’un segment de même couleur. 玛德琳 veut maximiser cette valeur, tandis que 坏德琳 veut la minimiser.

Énoncé

Alice et Bob jouent à un jeu sur une suite de longueur $n$. Chaque élément de la suite ne peut valoir que $0$ ou $1$, et l’instant auquel sa valeur est fixée est déterminé avant le début du jeu.

On vous donne deux suites $p$ et $a$ de longueur $n$, où $p$ est une permutation de $1\dots n$ et $a_i\in\{-2,-1,0,1\}$.

La valeur du $i$-ième élément de la suite est fixée à l’instant $p_i$, selon les règles suivantes :

• Si $a_i=0$, cet élément reçoit la valeur $0$ ;
• si $a_i=1$, cet élément reçoit la valeur $1$ ;
• si $a_i=-1$, Alice choisit la valeur de cet élément à cet instant ;
• si $a_i=-2$, Bob choisit la valeur de cet élément à cet instant.

Avant le début du jeu, Alice et Bob connaissent tous deux les suites $p$ et $a$. Le jeu comporte $n$ instants. À l’instant $k$, on fixe la valeur à la position $i$ telle que $p_i=k$ ; au terme de ces $n$ instants, la valeur de chaque élément de la suite a été fixée exactement une fois.

Un segment contigu monochrome est défini par un couple $(l,r)$ tel que $l\le r$ et que tous les éléments du $l$-ième au $r$-ième aient la même valeur. S’il ne peut être prolongé ni vers la gauche ni vers la droite (c’est-à-dire si $l=1$ ou si l’élément en position $l-1$ a une valeur différente, et si $r=n$ ou si l’élément en position $r+1$ a une valeur différente), on l’appelle un segment contigu monochrome maximal. La longueur de $(l,r)$ est $r-l+1$.

Alice souhaite maximiser la longueur maximale des segments contigus monochromes maximaux de la suite après l’instant $n$, tandis que Bob souhaite minimiser cette valeur.

On vous donne un entier strictement positif $typ \in \{1,2\}$.

Si $typ=1$, les deux joueurs suivent une stratégie optimale. Déterminez la longueur maximale des segments contigus monochromes maximaux de la suite finale. On peut démontrer que la réponse est déterminée de manière unique.

Si $typ=2$, on vous donne également une suite $A$ de longueur $n$. La valeur $A_i \in \{0,1\}$ décrit la décision prise à l’instant $i$ du jeu : soit $x$ l’unique entier strictement positif parmi $1,2,\dots,n$ tel que $p_x=i$ ; on affecte alors la valeur $A_i$ au $x$-ième élément de la suite (il est possible qu’un rayon cosmique frappe la position $x$, de sorte que $a_x,A_i \in \{0,1\}$ mais $a_x \neq A_i$). Pour chaque $i=0,1,\dots,n$, déterminez la longueur $ans_i$ du plus long segment contigu monochrome de la suite finale si, jusqu’à l’instant $i$ inclus, le jeu suit les décisions de la suite $A$, puis si les deux joueurs suivent une stratégie optimale après la fin de l’instant $i$.

Entrée

Ce problème impose un traitement en ligne.

La première ligne contient un entier strictement positif $T$, le nombre de cas de test.

Viennent ensuite $T$ cas de test. Pour chacun :

La première ligne contient deux entiers strictement positifs $n$ et $typ$.

La deuxième ligne contient $n$ entiers $p_1,p_2,\dots,p_n$.

La troisième ligne contient $n$ entiers $a_1,a_2,\dots,a_n$.

Si $typ=2$, la quatrième ligne contient $n$ entiers $A'_1,A'_2,\dots,A'_n$.

La véritable valeur de $A_i$ est le résultat du XOR bit à bit de $A'_i$ et de $ans_{i-1}$, pris modulo $2$.

Sortie

Pour chaque cas de test :

Si $typ=1$, affichez sur une ligne un entier : la longueur du plus long segment contigu monochrome de la suite finale lorsque les deux joueurs suivent une stratégie optimale.

Si $typ=2$, affichez sur une ligne $n+1$ entiers : pour chaque $i=0,1,\dots,n$, la longueur du plus long segment contigu monochrome de la suite finale si, jusqu’à l’instant $i$ inclus, le jeu suit les décisions de la suite $A$, puis si les deux joueurs suivent une stratégie optimale après la fin de l’instant $i$.

Exemples

Entrée 1

1
3 1
3 1 2
-1 -2 -1

Sortie 1

3

Remarque

$p=[3,1,2]$ signifie que $p_1=3,\ p_2=1,\ p_3=2$ : le $1$-er élément est fixé à l’instant $3$, le $2$-ième à l’instant $1$ et le $3$-ième à l’instant $2$. L’ordre chronologique est donc le suivant :

• Instant $1$ : on fixe le $2$-ième élément ($a_2=-2$, Bob décide) ;
• instant $2$ : on fixe le $3$-ième élément ($a_3=-1$, Alice décide) ;
• instant $3$ : on fixe le $1$-er élément ($a_1=-1$, Alice décide).

Alice veut que le plus long segment monochrome soit aussi long que possible, tandis que Bob le veut aussi court que possible. Bob joue en premier, mais ne contrôle que le $2$-ième élément, au milieu ; Alice contrôle les éléments $1$ et $3$, aux deux extrémités.

Si Bob fixe le $2$-ième élément à $0$, Alice peut également fixer les éléments $1$ et $3$ à $0$ ; la suite finale est alors 0 0 0 et la longueur du plus long segment monochrome est $3$. Si Bob fixe le $2$-ième élément à $1$, Alice choisit également $1$ pour les deux autres ; la suite finale est 1 1 1 et la longueur du plus long segment monochrome est encore $3$.

Les deux choix de Bob aboutissent exactement au même résultat : il ne peut pas faire descendre la réponse en dessous de $3$. De son côté, Alice peut tout au plus rendre toute la suite monochrome. La réponse est donc $3$.

Entrée 2

1
2 1
2 1
-1 -1

Sortie 2

2

Remarque

$p=[2,1]$ signifie que $p_1=2,\ p_2=1$ : le $1$-er élément est fixé à l’instant $2$ et le $2$-ième à l’instant $1$. La valeur de $a$ est $-1$ pour les deux éléments ; Alice décide donc pour les deux :

• Instant $1$ : on fixe le $2$-ième élément ($a_2=-1$, Alice décide) ;
• instant $2$ : on fixe le $1$-er élément ($a_1=-1$, Alice décide).

Alice souhaite maximiser la longueur du plus long segment monochrome. Comme elle choisit la valeur des deux éléments, il lui suffit de leur attribuer la même valeur pour obtenir 0 0 ou 1 1. Dans ce cas, $(1,2)$ est un segment contigu monochrome maximal de longueur $2$. La suite entière n’ayant qu’une longueur de $2$, c’est également le meilleur résultat qu’elle puisse obtenir.

Entrée 3

3
2 1
1 2
-1 -2
4 2
1 3 2 4
-1 0 -2 -1
1 0 0 1
3 1
3 1 2
0 0 1

Sortie 3

1
2 2 3 2 2
2

Contraintes

Des dépendances appropriées entre sous-tâches sont activées pour ce problème.

Pour tous les cas de test, les garanties suivantes s’appliquent :

• $1 \leq T \leq 2 \times 10^5$, $1\le n\le 2\times 10^5$, $1 \le typ \le 2$, $1 \leq \sum n \leq 2 \times 10^5$.

• $p$ est une permutation de $1\dots n$.

• $a_i\in\{-2,-1,0,1\}$.

• $A_i\in\{0,1\}$.

Propriété particulière A : il est garanti que $a_i\in\{0,1\}$.

Propriété particulière B : il est garanti que $p$ et $a$ sont générées aléatoirement parmi les suites de longueur $n$ respectant les contraintes.

Remarque : les sous-tâches $3,4,5,8,9$ dépendent de la sous-tâche $2$.