Les quelques kapokiers du jardin natal continuent de pousser dans les souvenirs de 小 N, qui s’estompent peu à peu. Ses souvenirs du jardin sont représentés par une suite $[a_0,a_1,\ldots,a_{n-1}]$ de longueur $n$.

Chaque kapokier a la forme d’un arbre non enraciné dont les nœuds sont étiquetés. Le souvenir d’un kapokier correspond à un intervalle $[l,r)$ de cette suite :

• L’arbre possède $k=r-l+2$ nœuds, numérotés de $0$ à $k-1$.
• Sa suite de Prüfer est $[\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)]$. La définition de la suite de Prüfer figure dans la section « Remarque ».

En se remémorant le passé, 小 N vous pose $m$ questions. La $i$-ième ($0\le i<m$) est :

• Dans le kapokier correspondant à l’intervalle $[l_i,r_i)$ de ses souvenirs, les nœuds $x_i,y_i$ sont-ils adjacents ?

Détails d'implémentation

Vous n’avez pas besoin d’implémenter la fonction main, et ne devez pas le faire.

Votre fichier source doit inclure l’en-tête kapok.h. Ajoutez donc au début du programme :

#include "kapok.h"

Vous devez implémenter dans le fichier source soumis kapok.cpp la fonction suivante :

std::vector<bool> kapok(int c, int n, int m,
   std::vector<int> a, std::vector<int> l, std::vector<int>
   r, std::vector<int> x, std::vector<int> y);

• $c,n,m$ sont respectivement le numéro du test, la longueur de la suite des souvenirs et le nombre de questions. $c=0$ indique un exemple.
• a représente la suite des souvenirs.
• l,r représentent les deux extrémités de l’intervalle donné pour chaque question.
• x,y représentent les deux numéros de nœuds donnés pour chaque question.
• La fonction doit retourner une suite $f_0,f_1,\ldots,f_{m-1}$ de longueur exactement $m$, où $f_i$ ($0\le i<m$) est le résultat de la $i$-ième question.
• Pour chaque test, l’évaluateur appelle cette fonction exactement une fois.

Le fichier template_kapok.cpp du répertoire du problème fournit un exemple de code que vous pouvez utiliser comme référence pour votre implémentation.

Tester votre programme

Vous pouvez compiler un exécutable dans le répertoire du problème avec la commande :

g++ grader.cpp kapok.cpp -o kapok -O2 -std=c++14 -static

L’exécutable kapok ainsi obtenu fonctionne comme suit :

• Il lit sur l’entrée standard les données suivantes :

  • La première ligne contient trois entiers non négatifs $c,n,m$.
  • La deuxième ligne contient $n$ entiers non négatifs $a_0,a_1,\ldots,a_{n-1}$.
  • La ligne $i+3$ ($0\le i<m$) contient quatre entiers non négatifs $l_i,r_i,x_i,y_i$.

• Il écrit sur la sortie standard les données suivantes :

  • La ligne $i+1$ ($0\le i<m$) contient un entier non négatif : 0 signifie que $f_i$ vaut false et 1 qu’il vaut true.

Exemples

Entrée 1

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

Sortie 1

1
0
1

Remarque

• L’intervalle $[0,3)$ correspond à un arbre de 5 nœuds, de suite de Prüfer $[2,0,2]$ et d’ensemble d’arêtes $\{(1,2),(0,3),(0,2),(2,4)\}$. Les nœuds $0,2$ sont donc adjacents.
• L’intervalle $[3,5)$ correspond à un arbre de 4 nœuds, de suite de Prüfer $[3,0]$ et d’ensemble d’arêtes $\{(1,3),(0,2),(0,3)\}$. Les nœuds $1,2$ ne sont donc pas adjacents.
• L’intervalle $[0,0)$ correspond à un arbre de 2 nœuds dont la suite de Prüfer est vide. Son unique arête est $(0,1)$ ; les nœuds $0,1$ sont donc adjacents.

Exemples 2

Voir kapok/kapok2.in et kapok/kapok2.ans dans le répertoire du candidat.

Cet exemple satisfait les contraintes des tests $3\sim5$.

Exemples 3

Voir kapok/kapok3.in et kapok/kapok3.ans dans le répertoire du candidat.

Cet exemple satisfait les contraintes des tests $3\sim5$.

Contraintes

Pour tous les tests :

• $1\le n,m\le2\times10^5$.
• Pour tout $0\le i<n$, $0\le a_i<n+2$.
• Pour tout $0\le i<m$, $0\le l_i\le r_i\le n$ et $0\le x_i,y_i<r_i-l_i+2$.

• Propriété particulière A : pour tout $0\le i<m$, une fois $l_i,r_i$ fixés, les couples ordonnés $x_i,y_i$ sont générés indépendamment et uniformément parmi tous ceux qui satisfont les restrictions.

Remarque

Pour un arbre non enraciné $T$ dont les nœuds sont numérotés de $0$ à $c-1$ ($c\ge2$) :

• Effectuez successivement $c-2$ opérations. La $i$-ième ($0\le i<c-2$) consiste à :

  • Trouver la feuille actuelle de plus petit numéro $v_i$.
  • Noter le numéro $p_i$ de son unique voisin.
  • Supprimer ensuite de $T$ le nœud $v_i$ et son unique arête incidente.

• La suite $[p_0,p_1,\ldots,p_{c-3}]$ de longueur $c-2$ ainsi obtenue est la suite de Prüfer de $T$.