1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Subtraction Game
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, games

You are given two positive integers, $$$a$$$ and $$$b$$$ ($$$a < b$$$).

For some positive integer $$$n$$$, two players will play a game starting with a pile of $$$n$$$ stones. They take turns removing exactly $$$a$$$ or exactly $$$b$$$ stones from the pile. The player who is unable to make a move loses.

Find a positive integer $$$n$$$ such that the second player to move in this game has a winning strategy. This means that no matter what moves the first player makes, the second player can carefully choose their moves (possibly depending on the first player's moves) to ensure they win.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The only line of each test case contains two integers, $$$a$$$ and $$$b$$$ ($$$1 \le a < b \le 100$$$).

Output format:
For each test case, output any positive integer $$$n$$$ ($$$1 \le n \le 10^6$$$) such that the second player to move wins.

It can be proven that such an $$$n$$$ always exists under the constraints of the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, when $$$n = 2$$$, the first player must remove $$$a = 1$$$ stone. Then, the second player can respond by removing $$$a = 1$$$ stone. The first player can no longer make a move, so the second player wins.

In the second test case, when $$$n = 6$$$, the first player has two options:

- If they remove $$$b = 5$$$ stones, then the second player can respond by removing $$$a = 1$$$ stone. The first player can no longer make a move, so the second player wins.
- If they remove $$$a = 1$$$ stone, then the second player can respond by removing $$$a = 1$$$ stone. Afterwards, the players can only alternate removing exactly $$$a = 1$$$ stone. The second player will take the last stone and win.

In the third test case, the first player cannot make any moves when $$$n = 3$$$, so the second player immediately wins.

Example input:
3
1 4
1 5
9 26

Example output:
2
6
3

Editorial:
We present two approaches.
Approach 1
If $$$a \ge 2$$$, then $$$n = 1$$$ works.
Else if $$$a = 1$$$ and $$$b \ge 3$$$, $$$n = 2$$$ works.
Otherwise, $$$a = 1$$$ and $$$b = 2$$$, so $$$n = 3$$$ works.
Approach 2
Printing $$$a+b$$$ works because no matter what move the first player makes, the second player can respond with the opposite move.
The time complexity is $$$\mathcal{O}(1)$$$ per test case.
Particles
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 1300
Tags: dp, greedy, implementation, math

You have discovered $$$n$$$ mysterious particles on a line with integer charges of $$$c_1,\dots,c_n$$$. You have a device that allows you to perform the following operation:

- Choose a particle and remove it from the line. The remaining particles will shift to fill in the gap that is created. If there were particles with charges $$$x$$$ and $$$y$$$ directly to the left and right of the removed particle, they combine into a single particle of charge $$$x+y$$$.

For example, if the line of particles had charges of $$$[-3,1,4,-1,5,-9]$$$, performing the operation on the $$$4$$$th particle will transform the line into $$$[-3,1,9,-9]$$$.

If we then use the device on the $$$1$$$st particle in this new line, the line will turn into $$$[1,9,-9]$$$.

You will perform operations until there is only one particle left. What is the maximum charge of this remaining particle that you can obtain?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$c_1,\dots,c_n$$$ ($$$-10^9 \le c_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output one integer, the maximum charge of the remaining particle.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the best strategy is to use the device on the $$$4$$$th particle, then on the $$$1$$$st particle (as described in the statement), and finally use the device on the new $$$3$$$rd particle followed by the $$$1$$$st particle.

In the second test case, the best strategy is to use the device on the $$$4$$$th particle to transform the line into $$$[998244353,998244353,1996488706]$$$, then on the $$$2$$$nd particle to transform the line into $$$[2994733059]$$$. Be wary of integer overflow.

In the third test case, there is only one particle, so no operations can be performed.

Example input:
3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718

Example output:
9
2994733059
-2718

Editorial:
Consider the set of even-indexed particles and the set of odd-indexed particles. Observe that particles can only ever combine with other particles from the same set. It follows that the answer is at most $$$$$$\max\left(\sum_{\text{odd }i} \max(c_i,0),\sum_{\text{even }i} \max(c_i,0)\right).$$$$$$
On the other hand, this bound is almost always obtainable. We can first perform the operation on all negatively charged particles in the same set as the desired final particle, then perform the operation on all the particles from the opposite set. There is a corner case where all particles are negative, where the answer is just $$$\max(c_1,\dots,c_n)$$$.
The time complexity is $$$\mathcal{O}(n)$$$.
Min Cost Permutation (Hard Version)
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 2800
Tags: binary search, constructive algorithms, data structures, greedy, math, sortings

The only difference between this problem and the easy version is the constraints on $$$t$$$ and $$$n$$$.

You are given an array of $$$n$$$ positive integers $$$a_1,\dots,a_n$$$, and a (possibly negative) integer $$$c$$$.

Across all permutations $$$b_1,\dots,b_n$$$ of the array $$$a_1,\dots,a_n$$$, consider the minimum possible value of $$$$$$\sum_{i=1}^{n-1} |b_{i+1}-b_i-c|.$$$$$$ Find the lexicographically smallest permutation $$$b$$$ of the array $$$a$$$ that achieves this minimum.

A sequence $$$x$$$ is lexicographically smaller than a sequence $$$y$$$ if and only if one of the following holds:

- $$$x$$$ is a prefix of $$$y$$$, but $$$x \ne y$$$;
- in the first position where $$$x$$$ and $$$y$$$ differ, the sequence $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$-10^9 \le c \le 10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,\dots,a_n$$$ ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers $$$b_1,\dots,b_n$$$, the lexicographically smallest permutation of $$$a$$$ that achieves the minimum $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it can be proven that the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$27$$$, and the permutation $$$b = [9,3,1,4,5,1]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this minimum: $$$|3-9-(-7)|+|1-3-(-7)|+|4-1-(-7)|+|5-4-(-7)|+|1-5-(-7)| = 1+5+10+8+3 = 27$$$.

In the second test case, the minimum possible value of $$$\sum\limits_{i=1}^{n-1} |b_{i+1}-b_i-c|$$$ is $$$0$$$, and $$$b = [1,3,5]$$$ is the lexicographically smallest permutation of $$$a$$$ that achieves this.

In the third test case, there is only one permutation $$$b$$$.

Example input:
3
6 -7
3 1 4 1 5 9
3 2
1 3 5
1 2718
2818

Example output:
9 3 1 4 5 1
1 3 5
2818

Editorial:
Satisfying Constraints
Contest: Codeforces Round 919 (Div. 2)
Difficulty rating: 800
Tags: brute force, greedy, math

Alex is solving a problem. He has $$$n$$$ constraints on what the integer $$$k$$$ can be. There are three types of constraints:

1. $$$k$$$ must be greater than or equal to some integer $$$x$$$;
2. $$$k$$$ must be less than or equal to some integer $$$x$$$;
3. $$$k$$$ must be not equal to some integer $$$x$$$.

Help Alex find the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints. It is guaranteed that the answer is finite (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). Also, it is guaranteed that no two constraints are the exact same.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$) — the number of constraints.

The following $$$n$$$ lines describe the constraints. Each line contains two integers $$$a$$$ and $$$x$$$ ($$$a \in \{1,2,3\}, \, 1 \leq x \leq 10^9$$$). $$$a$$$ denotes the type of constraint. If $$$a=1$$$, $$$k$$$ must be greater than or equal to $$$x$$$. If $$$a=2$$$, $$$k$$$ must be less than or equal to $$$x$$$. If $$$a=3$$$, $$$k$$$ must be not equal to $$$x$$$.

It is guaranteed that there is a finite amount of integers satisfying all $$$n$$$ constraints (there exists at least one constraint of type $$$1$$$ and at least one constraint of type $$$2$$$). It is also guaranteed that no two constraints are the exact same (in other words, all pairs $$$(a, x)$$$ are distinct).

Output format:
For each test case, output a single integer — the number of integers $$$k$$$ that satisfy all $$$n$$$ constraints.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$k \geq 3$$$ and $$$k \leq 10$$$. Furthermore, $$$k \neq 1$$$ and $$$k \neq 5$$$. The possible integers $$$k$$$ that satisfy the constraints are $$$3,4,6,7,8,9,10$$$. So the answer is $$$7$$$.

In the second test case, $$$k \ge 5$$$ and $$$k \le 4$$$, which is impossible. So the answer is $$$0$$$.

Example input:
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001

Example output:
7
0
90
0
0
800000000

Editorial:
Let's first only consider the $$$\geq$$$ and $$$\leq$$$ constraints. The integers satisfying those two constraints will be some contiguous interval $$$[l, r]$$$. To find $$$[l,r]$$$, for each $$$\geq x$$$ constraint, we do $$$l := \max{(l, x)}$$$ and for each $$$\leq x$$$ constraint, we do $$$r := \min{(r, x)}$$$.
Now, for each, $$$\neq x$$$ constraint, we check if $$$x$$$ is in $$$[l, r]$$$. If so, we subtract one from the answer (remember that there are no duplicate constraints). Let the total number of times we subtract be $$$s$$$. Then our answer is $$$\max{(r-l+1-s,0)}$$$. The time complexity of this solution is $$$O(n)$$$.
Summation Game
Contest: Codeforces Round 919 (Div. 2)
Difficulty rating: 1100
Tags: games, greedy, math, sortings

Alice and Bob are playing a game. They have an array $$$a_1, a_2,\ldots,a_n$$$. The game consists of two steps:

- First, Alice will remove at most $$$k$$$ elements from the array.
- Second, Bob will multiply at most $$$x$$$ elements of the array by $$$-1$$$.

Alice wants to maximize the sum of elements of the array while Bob wants to minimize it. Find the sum of elements of the array after the game if both players play optimally.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$k$$$, and $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — the number of elements in the array, the limit on the number of elements of the array that Alice can remove, and the limit on the number of elements of the array that Bob can multiply $$$-1$$$ to.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the sum of elements of the array after the game if both players play optimally.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, it is optimal for Alice to remove the only element of the array. Then, the sum of elements of the array is $$$0$$$ after the game is over.

In the second test case, it is optimal for Alice to not remove any elements. Bob will then multiply $$$4$$$ by $$$-1$$$. So the final sum of elements of the array is $$$3+1+2-4=2$$$.

In the fifth test case, it is optimal for Alice to remove $$$9, 9$$$. Bob will then multiply $$$5, 5, 3$$$ by $$$-1$$$. So the final sum of elements of the array is $$$-5-5-3+3+3+2=-5$$$.

Example input:
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3

Example output:
0
2
0
3
-5
-9
0
-1

Editorial:
It is optimal for Bob to negate the $$$x$$$ largest elements of the array. So in order to minimize the damage Bob will do, Alice should always remove some number of largest elements.
To solve the problem, we can sort the array and iterate over $$$i$$$ ($$$0 \leq i \leq k$$$) where $$$i$$$ is the number of elements Alice removes. For each $$$i$$$, we know that Alice will remove the $$$i$$$ largest elements of the array and Bob will negate the $$$x$$$ largest remaining elements so the sum at the end (given $$$i$$$ Alice removals) can be calculated fast with prefix sums, two pointers, or any similar approach. The time complexity is $$$O(n \log n)$$$ because of sorting.
Square String?
Contest: Codeforces Round 762 (Div. 3)
Difficulty rating: 800
Tags: implementation, strings

A string is called square if it is some string written twice in a row. For example, the strings "aa", "abcabc", "abab" and "baabaa" are square. But the strings "aaa", "abaaab" and "abcdabc" are not square.

For a given string $$$s$$$ determine if it is square.

Input format:
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) —the number of test cases.

This is followed by $$$t$$$ lines, each containing a description of one test case. The given strings consist only of lowercase Latin letters and have lengths between $$$1$$$ and $$$100$$$ inclusive.

Output format:
For each test case, output on a separate line:

- YES if the string in the corresponding test case is square,
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
10
a
aa
aaa
aaaa
abab
abcabc
abacaba
xxyy
xyyx
xyxy

Example output:
NO
YES
NO
YES
YES
YES
NO
NO
NO
YES

Editorial:
If the length of the given string $$$s$$$ is odd, then the answer is NO, since adding two strings cannot do that. Otherwise, let $$$n$$$ be the length of the string. Let's go through the first half of the string, comparing whether its first and $$$\frac{n}{2} + 1$$$ characters are equal, its second and $$$\frac{n}{2} + 2$$$ characters are equal, and so on. If the characters in any pair are not equal, the answer is NO, otherwise — YES.
Squares and Cubes
Contest: Codeforces Round 762 (Div. 3)
Difficulty rating: 800
Tags: implementation, math

Polycarp likes squares and cubes of positive integers. Here is the beginning of the sequence of numbers he likes: $$$1$$$, $$$4$$$, $$$8$$$, $$$9$$$, ....

For a given number $$$n$$$, count the number of integers from $$$1$$$ to $$$n$$$ that Polycarp likes. In other words, find the number of such $$$x$$$ that $$$x$$$ is a square of a positive integer number or a cube of a positive integer number (or both a square and a cube simultaneously).

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of test cases.

Then $$$t$$$ lines contain the test cases, one per line. Each of the lines contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output format:
For each test case, print the answer you are looking for — the number of integers from $$$1$$$ to $$$n$$$ that Polycarp likes.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
6
10
1
25
1000000000
999999999
500000000

Example output:
4
1
6
32591
32590
23125

Editorial:
We'll search for positive integers not larger than $$$n$$$, and add their squares or cubes to the set if they don't exceed $$$n$$$. If $$$n = 10^9$$$, the maximum number Polycarp will like is $$$31622^2 = 999950884$$$, so the running time will be within the time limit.
The answer to the problem is the length of the resulting set.
MEX and Increments
Contest: Codeforces Round 762 (Div. 3)
Difficulty rating: 1700
Tags: constructive algorithms, data structures, dp, greedy, implementation, math, sortings

Dmitry has an array of $$$n$$$ non-negative integers $$$a_1, a_2, \dots, a_n$$$.

In one operation, Dmitry can choose any index $$$j$$$ ($$$1 \le j \le n$$$) and increase the value of the element $$$a_j$$$ by $$$1$$$. He can choose the same index $$$j$$$ multiple times.

For each $$$i$$$ from $$$0$$$ to $$$n$$$, determine whether Dmitry can make the $$$\mathrm{MEX}$$$ of the array equal to exactly $$$i$$$. If it is possible, then determine the minimum number of operations to do it.

The $$$\mathrm{MEX}$$$ of the array is equal to the minimum non-negative integer that is not in the array. For example, the $$$\mathrm{MEX}$$$ of the array $$$[3, 1, 0]$$$ is equal to $$$2$$$, and the array $$$[3, 3, 1, 4]$$$ is equal to $$$0$$$.

Input format:
The first line of input data contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input.

The descriptions of the test cases follow.

The first line of the description of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — elements of the array $$$a$$$.

It is guaranteed that the sum of the values $$$n$$$ over all test cases in the test does not exceed $$$2\cdot10^5$$$.

Output format:
For each test case, output $$$n + 1$$$ integer — $$$i$$$-th number is equal to the minimum number of operations for which you can make the array $$$\mathrm{MEX}$$$ equal to $$$i$$$ ($$$0 \le i \le n$$$), or -1 if this cannot be done.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first set of example inputs, $$$n=3$$$:

- to get $$$\mathrm{MEX}=0$$$, it is enough to perform one increment: $$$a_1$$$++;
- to get $$$\mathrm{MEX}=1$$$, it is enough to perform one increment: $$$a_2$$$++;
- $$$\mathrm{MEX}=2$$$ for a given array, so there is no need to perform increments;
- it is impossible to get $$$\mathrm{MEX}=3$$$ by performing increments.

Example input:
5
3
0 1 3
7
0 1 2 3 4 3 2
4
3 0 0 0
7
4 6 2 3 5 0 5
5
4 0 1 0 4

Example output:
1 1 0 -1 
1 1 2 2 1 0 2 6 
3 0 1 4 3 
1 0 -1 -1 -1 -1 -1 -1 
2 1 0 2 -1 -1

Editorial:
First, let's sort the array. Then we will consider its elements in non-decreasing order. To make MEX equal to $$$0$$$, you need to increase all zeros. To make MEX at least $$$n$$$, you first need to make MEX at least $$$n - 1$$$, and then, if the number $$$n - 1$$$ is missing in the array, you need to get it. If there are no extra values less than $$$n - 1$$$, then this and all subsequent MEX values cannot be obtained. Otherwise, you can use the maximum of the extra array values. To do this, you can use a data structure such as a stack. If an element occurs more than once in the array, put its extra occurrences on the stack.
Permutation and Queries
Contest: Codeforces Round 762 (Div. 3)
Difficulty rating: 2400
Tags: brute force, data structures, divide and conquer, two pointers

You are given a permutation $$$p$$$ of $$$n$$$ elements. A permutation of $$$n$$$ elements is an array of length $$$n$$$ containing each integer from $$$1$$$ to $$$n$$$ exactly once. For example, $$$[1, 2, 3]$$$ and $$$[4, 3, 5, 1, 2]$$$ are permutations, but $$$[1, 2, 4]$$$ and $$$[4, 3, 2, 1, 2]$$$ are not permutations. You should perform $$$q$$$ queries.

There are two types of queries:

- $$$1$$$ $$$x$$$ $$$y$$$ — swap $$$p_x$$$ and $$$p_y$$$.
- $$$2$$$ $$$i$$$ $$$k$$$ — print the number that $$$i$$$ will become if we assign $$$i = p_i$$$ $$$k$$$ times.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$).

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$.

Each of the next $$$q$$$ lines contains three integers. The first integer is $$$t$$$ ($$$1 \le t \le 2$$$) — type of query. If $$$t = 1$$$, then the next two integers are $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \ne y$$$) — first-type query. If $$$t = 2$$$, then the next two integers are $$$i$$$ and $$$k$$$ ($$$1 \le i, k \le n$$$) — second-type query.

It is guaranteed that there is at least one second-type query.

Output format:
For every second-type query, print one integer in a new line — answer to this query.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first example $$$p = \{5, 3, 4, 2, 1\}$$$.

The first query is to print $$$p_3$$$. The answer is $$$4$$$.

The second query is to print $$$p_{p_1}$$$. The answer is $$$1$$$.

The third query is to swap $$$p_1$$$ and $$$p_3$$$. Now $$$p = \{4, 3, 5, 2, 1\}$$$.

The fourth query is to print $$$p_{p_1}$$$. The answer is $$$2$$$.

Example input:
5 4
5 3 4 2 1
2 3 1
2 1 2
1 1 3
2 1 2

Example output:
4
1
2

Example input:
5 9
2 3 5 1 4
2 3 5
2 5 5
2 5 1
2 5 3
2 5 4
1 5 4
2 5 3
2 2 5
2 5 1

Example output:
3
5
4
2
3
3
3
1

Editorial:
Let's compute an array $$$a$$$ of $$$n$$$ integers — answers to all possible second-type queries with $$$k = Q$$$, $$$Q ≈ \sqrt n$$$. Now, if we have to perform any second-type query, we can split it into at most $$$n / Q$$$ queries with $$$k = Q$$$ and at most $$$Q - 1$$$ queries with $$$k = 1$$$.
Let's also compute an array $$$r$$$ of $$$n$$$ integers — reverse permutation. If $$$p_i = j$$$, then $$$r_j = i$$$.
To perform any first-type query, we should recompute $$$p$$$, $$$r$$$ and $$$a$$$. We can swap $$$p_x$$$ and $$$p_y$$$ in the array $$$p$$$ and $$$r_{p_x}$$$ and $$$r_{p_y}$$$ in the array $$$r.$$$ No more than $$$2 \cdot Q$$$ elements will be changed in the array $$$a$$$. These are elements with indexes $$$x, r_x, r_{r_x}, \dots $$$($$$Q$$$ elements) and $$$y, r_y, r_{r_y}, \dots $$$($$$Q$$$ elements). We can recompute $$$a_x$$$ and then assign $$$a_{r_x} = r_{a_x}$$$ and $$$x = r_x$$$ $$$Q - 1$$$ times. Similarly for $$$y$$$.
Time complexity: $$$O((n+q)\sqrt n)$$$.