Well, this is a tough round...

A. Bender Problem

The description of this problem might seem to be a little bit complicated, however, it turns out to be not that difficult as it looks like. Using a mathematical language, at first we have n points, and they can be connected only in the order as they are given. Then, we have m segments, and for each of them, we can fold it at any points to form an angle of 90 degrees. The problem asks to find out whether it is feasible to connect all the given points by using the provided m segments while any folded position must overlap with some one of the given points.

Suppose that we connect the n points (0,1,2,...,n-1) in the order as they are given, and denote the segments as a[0],a[1],...a[n-1]. Now, we consider the condition under which the given n points can be precisely connected by only using the provided segments. As the segment is folded at some position, it can cover exactly two segments of a[0],a[1],...a[n-1]. Thus, we have the following two cases.

1) (a[0],a[1]), (a[2],a[3]),...,(a[n-2],a[n-1]) are paired, which implies that we should have segments whose length is a[0]+a[1], a[2]+a[3],....,a[n-2]+a[n-1]. Therefore, we can check whether the provided m segments contain all the requested length, and if it is "YES", the folded position is thus 1,3,5,...,n-1;

2) (a[1],a[2]), (a[3],a[4]),...,(a[n-3],a[n-2]), (a[n-1],a[0]) are paired, which means that the provided m segments contain the length a[1]+a[2], a[3]+a[4], .... a[n-1]+a[0], the answer is "YES", and the folded position is 2,4,6,...,n-2,0;

As the maximum length is no longer than 200 000, we can adopt the hash idea to store the number of rods for some given length, and check whether one the above two cases can be satisfied.

B. pSort

At first, we provide some claims which might help to understand the problem. We use A->B->C to denote that A can directly interchange with B, but cannot directly interchange with C.

Claim 1: Suppose that a chain A->X[1]->X[2]->....->X[m]->B exists for some integer m. Then, we can interchange A with B without changing the positions of the other elements.

Proof: As A->X[1]->X[2]->....->X[m]->B, by first interchanging A with X[1], we obtain X[1],A,X[2],....,X[m],B. By repeating the above operations for m+1 times, we have X[1],X[2],....,X[m],B,A. Then, we interchange B with X[m] to get X[1],X[2],....,B,X[m],A, and by repeating this operation for m times, we arrive at the state B,X[1],X[2],...,A.

According to the problem, the i-th cell can interchange with cells i+di and i-di, while take care that these two positions may not be reasonable (out of the range). Therefore, we can form one or several independent chains as in Claim 1. The given permutation in fact asks to interchange some A with B while not affecting the other elements. According to Claim 1, if both A and B belong to the same chain, they can successfully interchange with each other. Thererfore, the problem is equivalent to finding out whether a pair of two elements that are requested to interchange with each other belongs to the same chain or not.

We can adopt the union-find idea to solve the problem. At first, the root of each element is itself, i.e., they belong to their own chain. When we deal with i and di, we may find that two elements can interchange with each other and thus should belong to the same chain. To achieve this, we find out the root of the two elements, and connect one root to the other one (which serves as the root does not matter). Finally, when we deal with the permutation sequence, we just check the roots of any two elements that should interchange with each other, and if they are the same, the ans is "YES"; otherwise it is "NO".