Could someone share the approach ? problem link
Use the property that permutations form a cycle. So, my approach was to find the inverse permutation C[i] such that B[i] = A_{C[i]}, C[i] can be found as C[P[i]] = i.
Now store all the cycles, all queries of type 1 are simple rotations. To answer query of type 2 and 3 first calculate the correct indices using number of rotations.
You can see my code. If you are unable to understand anything, feel free to ask.
4 Likes
I think you can solve it by dividing the permutation b into cycles and storing a count of number of type-1 queries, then for finding the array element at any index you can just return the A_i at the index j where j=(i+number \ of \ type-1 \ queries)\%cycle \ size
2 Likes
How do we handle swaps then? And wont’t then your approach give TLE?
now it won’t it’s just a constant time operation. Find the indices and swap the array elements…
Have a look on my code , just above your comment
how i can solve chef and subarray problem ? my solution you can find here https://www.codechef.com/viewsolution/46828687
any help please
I think you’ve linked the code for second problem
Yeah I edited it
Could you please take an example. That will clear my doubt fast
WLOG, Sharing an example with array A elements >= n for clarity
A: 6 7 8 9 10
P: 5 1 4 3 2
Here, cycles are (2 5 1) ( 3 4). i.e. observe how element at position 2 changes after multiple type 1 operations.
Iter 1: 7 10 9 8 10
Iter 2: 10 6 8 9 7
Iter 3: 6 7 9 8 10
Notice how element at position two changes: 7 ( Initial Idx 2 ) → 10 ( Initial Idx 5 ) → 6 ( Initial Idx 1 ) → 7 ( Initial Idx 2 )
We can use this property of cycles to figure out which element will be present at the target idx after a set of type 1 operations.
1 Like
I’ll explain with sample only. The permutation is P = [2, 3, 1] and A = [1, 2, 3]. The inverse permutation can be calculated using C[P[i]] = i, so we get C = [3, 1, 2]. Now note that this permutation C has cycle (1 -> 3 -> 2 -> 1). This cycle has a length of 3. We can store all the cycles. In my code, I am storing cycles in comp[l].
Now let’s talk about query, we have query of type 1, so we increment a variable ones by 1.
Next we need to swap 2 and 3. But remember that we need to rotate 2 and 3 by ones. Looking at permutation cycle of C, we have 2 -> 1, 3 -> 2. So in original array A, we need to swap A[1] and A[2]. So array becomes [2, 1, 3].
Next query was type 3 with index as 1. So rotating by ones in the permutation we have 1 -> 3. We then output A[3] = 3.
To rotate in O(1), we can use length of cycles.
Is it clear now?
2 Likes
I did by binary lifting kind of thing, just calculated which element will where after 2 ^i shifts, then for each query position of element after j shifts can be found in log n time
1 Like
Can you please share your code . I also tried the same way but getting WA! 
Neat
struct lift
{
vector<vector<int>> next;
int delta;
lift(int n, int *b)
{
delta = 0;
next = vector<vector<int>>(18, vector<int>(n));
for (int i = 0; i < n; i++)
{
next[0][b[i] - 1] = i;
}
for (int i = 1; i < 18; i++)
{
for (int j = 0; j < n; j++)
{
next[i][j] = next[i - 1][next[i - 1][j]];
}
}
}
int get(int ret)
{
for (int j = 0; j < 18; j++)
{
if (delta & (1 << j))
{
ret = next[j][ret];
}
}
return ret;
}
};
void solve()
{
int n;
cin >> n;
int a[n];
int b[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int j = 0; j < n; j++)
{
cin >> b[j];
}
lift d(n, b);
int q;
cin >> q;
while (q--)
{
int x;
cin >> x;
if (x == 1)
{
d.delta++;
}
else if (x == 2)
{
int y, z;
cin >> y >> z;
y--;
z--;
y = d.get(y);
z = d.get(z);
swap(a[y], a[z]);
}
else
{
int y;
cin >> y;
y--;
y = d.get(y);
cout << a[y] << "\n";
}
}
}