Sim-4-2 | Swap N' Mex

This was the problem page during the contest. Access the current page here.
Time limit: 1.5s Memory limit: 512MB Input: Output:

Cerință

Sunt date două permutări AA și BB. Gestionați următoarele actualizări:

  • Vi se dă un număr ii (1i<N1 \leq i < N). Trebuie să interschimbați AiA_i cu Ai+1A_{i+1}.
  • Vi se dă un număr ii (1i<N1 \leq i < N). Trebuie să interschimbați BiB_i cu Bi+1B_{i+1}.

După fiecare actualizare, trebuie să spuneți dacă următoarea condiție este îndeplinită:

  • pentru fiecare 1ijN1 \le i \le j \le N, mex1([Ai,Ai+1,...,Aj])=mex([Bi,Bi+1,...,Bj])mex^{1}([A_i,A_{i+1},...,A_j]) = mex([B_i,B_{i+1},...,B_j]).

1: mex([A1,A2,...,AN])^{1}: \ mex([A_1,A_2,...,A_N]) reprezintă cel mai mic număr întreg x1x \ge 1 ce nu apare printre A1,A2,...,ANA_1,A_2,...,A_N.

Date de intrare

Pe prima linie se află două numere întregi NN și QQ --- lungimea celor două permutări și numărul de actualizări.

Pe a doua linie se află NN numere întregi care descriu permutarea AA.

Pe a treia linie se află NN numere întregi care descriu permutarea BB.

Pe următoarele QQ linii se vor afla câte două numere întregi tt și ii --- tipul actualizării dorite și indicele pe care se face actualizarea.

Date de ieșire

Ieșirea va consta din QQ linii --- după fiecare actualizare, dacă condiția dată în enunț este îndeplinită, afișați yes, în caz contrar afișați no pe linii separate. Rețineți că ieșirea nu este sensibilă la majuscule.

Restricții și precizări

  • 2N21052 \leq N \leq 2 \cdot 10^5;
  • 1Q21051 \le Q \le 2 \cdot 10^5;
  • 1AiN1 \leq A_i \leq N;
  • 1BiN1 \leq B_i \leq N;
  • t=1t = 1 sau t=2t = 2;

Subtask-uri

# Punctaj Restricții
0 0 Exemplul
1 13 1n,q501 \leq n,q \leq 50
2 21 1n,q5001 \leq n,q \leq 500
3 26 1n,q50001 \leq n,q \leq 5000
4 40 Fără restricții suplimentare

Exemplu

stdin

4 3
1 4 3 2
1 4 3 2
1 2
2 2
1 1

stdout

yes
yes
no

Explicație

După prima schimbare, permutările devin [1,3,4,2][1,3,4,2] și [1,4,3,2][1,4,3,2], satisfăcând condiția din enunț.

După a doua schimbare, permutările devin ambele [1,3,4,2][1,3,4,2], satisfăcând condiția din enunț.

După a treia schimbare, permutările devin [3,1,4,2][3,1,4,2] și [1,3,4,2][1,3,4,2]. Condiția nu este îndeplinită deoarece mex([3])mex([1])mex([3]) \neq mex([1]).

Log in or sign up to be able to send submissions!