I'll post it after it gets AC.

Mine is more or less the same big idea as I_Love_Tina's, but the details might be different. I only managed to finish coding after the contest was over :(

Here's my solution accepted in analysis mode (runs in 0.72s): Click

You will maintain edges in a compressed form. Let the k^th ancestor of vertex x be f[k][x]. You will maintain an array E[x][y] that is marked if all the edges on the path from vertex y to vertex f[2^x][y] are equal. Now if you have that all edges from vertex x to vertex f[k][x] are equal then pick up the largest t with 2^t ≤ k and mark E[t][x] and E[t][f[k - 2^t][x]]. Now if E[t][x] is marked you can say that E[t - 1][x] and E[t - 1][f[2^t - 1][x]] are marked and the edges (f[2^t - 1 - 1][x], f[2^t - 1][x]) and (f[2^t - 1][x], f[2^t - 1 + 1][x]) have the same direction. This way you can reduce the edges in .

Well if we had no updates we could solve the problem like that:

For every position i find rightmost position r_i such that gcd(i, r_i) > 1.

Now the answer for a query [L;R] is ( (sum of r values in [L;R]) — (sum of r values in [L;R] greater than R) + (count of r values in [L;R] greater than R) * R — R * (R + 1) / 2 + (L * (L - 1) / 2)).

Well this can be done with a merge sort tree in .

Now how to handle updates?

Well we go through the O(log(10⁹)) ranges from the previous comment. Now with binary search in segment tree we find for each of the ranges the corresponding r value. You can see that this r value will be the same for all of the positions in a given range. Well now we simply set the values in the range to r.

The data structure we will use will be merge sort tree with treap in every node, because using it the set operation of an interval can be done easily.

The complexity will be .

OPS I explained how to find the closest position to the right, not to the left, but the idea to find the one to the left is basically the same.

You do the binary search inside the segment tree:

Let's get the nodes in the segment tree which the query [i;N] will cover. They will obviously be at most . Now we begin from the leftmost such interval and go through these nodes.

If the interval of the current node is [L;R] we can easily find gcd(i, R) in O(1) using the gcd values of the previous intervals.

We find the first interval, such that gcd(i, R) = 1. This will be done in time.

Well now we know that the position which we are searching for (current j) is in a given interval [L;R] (we also know the number of this node in the segment tree).

Well we just start going down from our current node:

If the GCD of the current gcd and the gcd of the left child is not 1, we go to the right child with the new gcd. Else we go to the left child with the same gcd.

Using this in the end we will be at the first position x with gcd(i, x) = 1. The complexity will be .

So overall complexity for finding the closest position to the right of a given position will be .

i found my mistake. But it will work

What about N, N - 1, ..., 1 test?

UPD No question anymore.

For each i, calculate i+a[i], and put it into buckets. The number of fixed points in the flipped subarray [L, R] is the number of indices between L and R that are in bucket L+R. (you can use binary search). You can see it in my code that I posted down.

r — (i — l + 1) + 1 = p[i]
r — i + l — 1 + 1 = p[i]
r + l = p[i] + i
also don't forget about fixed points that are not inside [L,R]

Calculate prefix sum of elements that are at begining in right position. For every element x there is only one y (element or position between 2 elements) so one of the options is to reverse array around y where x is last element we reverse.Now for every y we try solutions and possible x are sorted (you processed from 1 to n) so just iterrate that list and substract number of elements that are at right position in that interval.